2.4 Sequences and Summations

Question 1

Sequence:

Answer 1

A sequence is a discrete structure used to represent an ordered list.
A sequence is a function from a subset of the set of integers (usually either the set {0, 1, 2, …}
or the set {1, 2, 3, …}) to a set S. We use the notation an to denote the image of the integer n.
We call an a term of the sequence

Question 2

Notation Of Sequence:

Answer 2

We use the notation {an} to describe the sequence. (Note that an represents an individual
term of the sequence {an}.

{an} used for set also but the context will make it clear.

Question 3

How do we describe sequences:

Answer 3

We describe sequences by listing the terms of the sequence in order of increasing subscripts.

Question 4

geometric progression:

Answer 4

A geometric progression is a sequence of the form
a, ar, ar^2, … , ar^n, …
where the initial term a and the common ratio r are real numbers

Question 5

Geometric progression is analogous to what?

Answer 5

A geometric progression is a discrete analogue of the exponential function f(x) = ar^x

Question 6

arithmetic progression

Answer 6

An arithmetic progression is a sequence of the form
a, a + d, a + 2d, … , a + nd, …
where the initial term a and the common difference d are real numbers.

Question 7

arithmetic progression analogous:

Answer 7

An arithmetic progression is a discrete analogue of the linear function f(x) = dx + a.

Question 8

Strings? and their length?

Answer 8

Sequences of the form a1, a2, … , an are often used in computer science. These finite sequences are also called strings. This string is also denoted by a1a2 … an. (Recall that bit strings, which are finite sequences of bits, were introduced in Section 1.1.)

The length of a string is the number of terms in this string.

Question 9

Empty String:

Answer 9

The empty string, denoted by 𝜆, is the string that has no terms.
The empty string has length zero.

Question 10

recurrence relation:

whats a solution to it:

Answer 10

A recurrence relation for the sequence {an} is an equation that expresses an in terms of
one or more of the previous terms of the sequence, namely, a0, a1, … , an−1, for all integers n
with n ≥ n0, where n0 is a nonnegative integer.

A sequence is called a solution of a recurrence
relation if its terms satisfy the recurrence relation.

(A recurrence relation is said to recursively
define a sequence. We will explain this alternative terminology in Chapter 5.)

Question 11

Initial Condition:

Comment on solution..

Answer 11

The initial conditions for a recursively defined sequence specify the terms that precede the first term where the recurrence relation takes effect.

Using mathematical induction, a proof technique introduced in Chapter 5, it can be shown that a recurrence relation together with its initial conditions determines a unique solution.

Question 12

Fibonacci sequence

Answer 12

The Fibonacci sequence, f0, f1, f2, … , is defined by the initial conditions f0 = 0, f1 = 1, and
the recurrence relation
fn = fn−1 + fn−2
for n = 2, 3, 4, … .

Chapters
5 and 8, where we will see why it is important for many applications, including modeling the
population growth of rabbits. Fibonacci numbers occur naturally in the structures of plants and
animals, such as in the arrangement of sunflower seeds in a seed head and in the shell of the
chambered nautilus.

Question 13

Closed Formula:

Answer 13

We say that we have solved the recurrence relation together with the initial conditions when
we find an explicit formula, called a closed formula, for the terms of the sequence.

Question 14

Iteration:

Forward and backward substitution:

Answer 14

We obtain the nth term after n − 1 iterations of the recurrence relation.

We have iterated, or repeatedly used,
the recurrence relation. The first approach is called forward substitution—we found successive
terms beginning with the initial condition and ending with an.

The second approach is called
backward substitution, because we began with an and iterated to express it in terms of falling
terms of the sequence until we found it in terms of a1.

Note that when we use iteration, we
essentialy guess a formula for the terms of the sequence. To prove that our guess is correct, we
need to use mathematical induction, a technique we discuss in Chapter 5.

Question 15

A common problem in discrete mathematics is finding a closed formula, a recurrence relation,
or some other type of general rule for constructing the terms of a sequence.

When trying to deduce a possible formula, recurrence relation, or some other type of rule
for the terms of a sequence when given the initial terms, try to find a pattern in these terms.

There are many questions you could ask, but some of the more useful are:
5

Answer 15

▶ Are there runs of the same value? That is, does the same value occur many times in a row?
▶ Are terms obtained from previous terms by adding the same amount or an amount that
depends on the position in the sequence?
▶ Are terms obtained from previous terms by multiplying by a particular amount?
▶ Are terms obtained by combining previous terms in a certain way?
▶ Are there cycles among the terms?

Question 16

Useful sequences:

Answer 16

nth Term First 10 Terms
n^2 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, …
n^3 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, …
n^4 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000, …
fn 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
2^n 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,…
3^n 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049,…
n! 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, …

Question 17

Lucas Sequence:

Answer 17

the sequence is determined by the
recurrence relation Ln = Ln−1 + Ln−2 with initial conditions L1 = 1 and L2 = 3

e French mathematician Franc¸ois Edouard Lucas. Lucas ´
studied this sequence and the Fibonacci sequence in the nineteenth century

Question 18

The kissing problem:

Answer 18

e kissing problem (a name he coined), which asks how many spheres can be
arranged in n dimensions so that they all touch a central sphere of the same size. (In two dimensions the answer is 6, because 6 pennies can be placed so that they touch a central penny. In three dimensions, 12 billiard
balls can be placed so that they touch a central billiard ball. Two billiard balls that just touch are said to “kiss,” giving rise to the
terminology “kissing problem” and “kissing number.”) Sloane, together with Andrew Odlyzko, showed that in 8 and 24 dimensions,
the optimal kissing numbers are, respectively, 240 and 196,560. The kissing number is known in dimensions 1, 2, 3, 4, 8, and 24, but
not in any other dimensions.

LOOK INTO IT!

Question 19

Summation:

and its terms, work.

Answer 19

To express the sum of the terms
am, am+1, … , an
from the sequence {an}. We use the notation
∑m≤j≤n aj
(read as the sum from j = m to j = n of aj) to represent
am + am+1 + ⋯ + an.

j: index of summation
j runs through all integers starting with its lower limit m and ending with its upper limit n.
Greek letter sigma, ∑.

The usual laws for arithmetic apply to summations. For example, when a and b are real
numbers, we have ∑ ( a(xj) ) = a∑ (xj)

CHECK IT

Question 20

Example 20:

shift the index of summation in a sum:

Answer 20

Sometimes it is useful to shift the index of summation in a sum.
When shifting an index
of summation, it is important to make the appropriate changes in the corresponding summand.

Question 21

Sums of terms of geometric progressions commonly arise (such sums are called geometric
series)

Answer 21

If a and r are real numbers and r ≠ 0, then
check the book.

Prove it.

Question 22

Comment on Double summations:

Answer 22

They are used in comp prog, analysis of nested loops..
∑∑ij.
You can solve them by expanding inner summation and then outer.

Question 23

A useful formula for summation:

Answer 23

table 2, 2.4. Page 176.

Question 24

⌊n∕2⌋ + ⌈n∕2⌉ comment on it?

Answer 24

Its always = n.

Question 25

Telescoping:

Answer 25

“telescopes”: each term cancels part of the term before it

that ∑n,j=1 (aj − aj−1) = an − a0,
where a0, a1,… , an is a sequence of real numbers. This type
of sum is called telescoping.

Question 26

A way to deal with sequences, find sums:

partial fractions ish…

Answer 26

1∕(k(k + 1)) = 1∕k − 1∕(k + 1)

Question 27

Notation for products:

Answer 27

There is also a special notation for products. The product of
am, am+1,… , an is represented by ∏n
j= m
aj
, read as the product
from j = m to j = n of aj
.