2.4 Sequences and Summations Flashcards
Sequence:
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
Notation Of Sequence:
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.
How do we describe sequences:
We describe sequences by listing the terms of the sequence in order of increasing subscripts.
geometric progression:
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
Geometric progression is analogous to what?
A geometric progression is a discrete analogue of the exponential function f(x) = ar^x
arithmetic progression
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.
arithmetic progression analogous:
An arithmetic progression is a discrete analogue of the linear function f(x) = dx + a.
Strings? and their length?
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.
Empty String:
The empty string, denoted by 𝜆, is the string that has no terms.
The empty string has length zero.
recurrence relation:
whats a solution to it:
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.)
Initial Condition:
Comment on solution..
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.
Fibonacci sequence
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.
Closed Formula:
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.
Iteration:
Forward and backward substitution:
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.
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
▶ 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?
Useful sequences:
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, …
Lucas Sequence:
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
The kissing problem:
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!
Summation:
and its terms, work.
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
Example 20:
shift the index of summation in a sum:
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.
Sums of terms of geometric progressions commonly arise (such sums are called geometric
series)
If a and r are real numbers and r ≠ 0, then
check the book.
Prove it.
Comment on Double summations:
They are used in comp prog, analysis of nested loops..
∑∑ij.
You can solve them by expanding inner summation and then outer.
A useful formula for summation:
table 2, 2.4. Page 176.
⌊n∕2⌋ + ⌈n∕2⌉ comment on it?
Its always = n.
Telescoping:
“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.
A way to deal with sequences, find sums:
partial fractions ish…
1∕(k(k + 1)) = 1∕k − 1∕(k + 1)
Notation for products:
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 .
