CMPS 2120 Week04 Lecture Notes - Sequences and Summations
resources:
summation formulae
khan academy
Notation: a_n denotes 'a' with subscript 'n' (reads "a sub n").
'Σ' is the Greek letter big-Sigma.
*******************
* SEQUENCES *
*******************
A sequence in a set A is a function f from a subset of integers (usually
{0,1,2,3....} or {1,2,3,4,....} to A. Values of a sequence are called terms.
The terms are denoted by subscript notation for terms; e.g.,
a_0, a_1, a_2, a_3,...a_n. (reads "a sub zero, a sub 1, a sub 2 ... a sub n)
EXAMPLE.
a_n = 1/n 1/1, 1/2, 1/3, 1/4, . . ., n >= 1
b_n = 2n 0, 2, 4, 6, 8, 10, . . ., n >= 0
c_n = n^2 0, 1, 4, 9, 16, . . ., n >= 0
Sequences can be defined by:
1. A recursive definition (based on previous terms with a starting term)
2. A closed form (a formula to determine any term given n)
You can often come up with both definitions if you start with a well-defined
sequence. Assume the underlying mapping for our sequences is N={0,1,2,3,...},
i.e., the first term in the sequence maps to zero (the math is often easier
this way).
EXAMPLE 1.
Find the recursive and closed form formulas for the sequence
1, 3, 5, 7, 9 ...
Recursive. Ask yourself "How do I come up with the next term in the sequence?"
It looks like you just add 2 the the previous term. Add in the starting value
and you have the recursive formula:
a_0 = 1. a_n = a_n-1 + 2, for n >= 1.
Closed form. Ask yourself "How do I come up with the ith term by just plugging
i into a formula? You need to find a pattern. Write down the sequence with n
above it:
0 1 2 3 4
1, 3, 5, 7, 9 ...
Ask yourself, how did I get to 9 from 4? How did I get to 7 from 3? Ahh..it
looks like 2n+1. Try a few. Generally, if 3 terms work you know you have it.
Closed Form Formula: a_n = 2n + 1, n >= 0.
EXAMPLE 2.
Find the recursive and closed form formulas for the sequence
1, 3, 7, 13, 21, 31, 43
This one is not so easy. Write down n above the sequence. Then subtract one
term from the next term until you see a pattern:
0 1 2 3 4 5 6
1, 3, 7, 13, 21, 31, 43
2 4 6 8 10 12
Ahh...it looks like a_n = a_(n-1) + 2n. Add an initial value and you have it.
Recursive Formula: a_0 = 1. a_n = a_n-1 + 2n, for n >= 1
The closed form is a little tougher. Note the following. Subtract terms in the
sequence that is left from the first subtraction:
0 1 2 3 4 5 6
1, 3, 7, 13, 21, 31, 43
2 4 6 8 10 12
2 2 2 2 2
Note that it takes two rounds of subtractions before you reach a constant
value (unlike Example 1). This means that the underlying closed form formula
to generate the sequence includes a quadratic (n^2) term.
Knowing that, try a few things that involve n^2 until you see a pattern.
For n=4, 21 is 16 + 5. For n=5, 31 is 25 + 6. For n=6, 43 is 36 + 7. Hmmmm...
it looks like n^2 + n + 1. Confirm with n=3: 9+4=13. check. n=0: 0+1=1. check.
You have it:
Closed Form Formula: a_n = n^2 + n + 1, n >= 0
EXAMPLE 3.
1 2 3 4 5 6
a = 1 8 27 64 125 216
7 19 37 61 91
12 18 24 30
6 6 6 << THREE SUBTRACTIONS
closed form formula is n^3, n > = 1.
IMPORTANT NOTE. If it takes three subtractions to get a constrant you
may also have a polynomial of degree 2 as the underlying function. If
you have an n^3 function it will always take at least three. If you have
a quadratic it will take at least 2.
EXAMPLE 3.
Construct the sequence given a recursive definition.
a_0 = 5. a_n = a_(n-1) - 3.
The sequence is:
5, 2, -1, -4, -7, -10 , -13, . .
Q: What is the 16th term?
We could brute force it, but let's try to come up with a closed form formula.
0 1 2 3 4 5 6
5, 2, -1, -4, -7, -10 , -13, . .
-3 -3 -3 -3 -3 -3
We know this is a linear and not a quadratic function.
Try a few things. For n=4, -7 is -2n + 1. That doesn't work for n=5. Look at
n=0. The ONLY way to get 5 is to add 5 to the formula. We know the formula has
to be +5. OK. This is what we have so far.
f(n) = xn + 5. (we do not know what x is)
Plug in a random f(n), say for n=3 and solve for x.
-4 = 3x + 5.
-9 = 3x
x = -3.
So our formula now is f(n) = -3n + 5. Try a few cases.
f(4) = -3*4 + 5
= -12 + 5
= -7. check.
f(6) = -3*6 + 5
= -18 + 5
= -13. check.
f(1) = -3 + 5
= 2. check
Closed Form Formula.
f(n) = -3n + 5, n >= 0.
-----------------------------------------------------------------------------
To generalize.
Arithmetic progressions are sequences over {0,1,2...n} of the form dn + a,
where 'a' is the beginning term and 'd' is a common difference between terms.
Arithmetic progressions describe discrete linear functions.
Example.
a_n = 3, 5, 7, 9, 11, ...
a_n = 2n + 3, n >= 0
For the sequence 1, 4, 7, 10, 13, 16, . . .
3 3 3 3 3
closed form: a_n = 3n + 1, n >= 0
recursion: a_n = a_n-1 + 3, a_0 = 1
If the difference between terms is not a constant, find the difference between
the difference. If you hit a constant you have a quadratic function.
Example.
For the sequence 1, 3, 7, 13, 21, 31,...
n 0 1 2 3 4 5
a_n 1 3 7 13 21 31
2 4 6 8 10
2 2 2 2 <- constant
a_n = n^2 + n + 1, n >= 0
Example.
For the sequence 5, 7, 11, 17, 25, ...
n 0 1 2 3 4
a_n 5 7 11 17 25
2 4 6 8
2 2 2 <= 2 levels before constant therefore a quadratic
closed form: a_n = n^2 + n + 5, n >= 0.
If the closed form is quadratic, the recursive definition is a summation of 2n:
a_0 = 5 a_n = a_n-1 + 2n
Ex. For the sequence 1 8 27 64 125 216
7 19 37 61 91
12 18 24 30
6 6 6 <= 3 levels so n^3
closed form: a_n = n^3, n >= 1
-----------------------------------------------------------------------------
Geometric progressions are sequences over {0,1,2...n} of the form ar^0, ar^1,
ar^2, ... ar^n, where 'a' is the beginning term and 'r' is a common ratio
between terms. Geometric progressions describe discrete exponentional
functions. For example, the following sequence, where r = 2 and a = 3,
3, 6, 12, 24, 48, ...
is defined by a_n = 3(2^n), n >= 0.
-------------------------------------------------------------------------------
*********************
* SUMMATIONS *
*********************
Def: A "summation" applies the addition operator to the terms in a sequence.
Ex.
If "1 2 3 4 5" is a sequence then "1+2+3+4+5" is the summation of that sequence.
Def: Let a_n be a sequence. Then big-Sigma notation is ('Σ' denotes big-Sigma):
n
Σ a_j where j is the index, m is the lower bound,
j=m n is the upper bound, and a_j is the summand
means the sum a_m + a_m+1 + a_m+2 + ... + a_n-1 + a_n
A summation can be expressed as a closed form formula:
n
Σ j = 1 + 2 + 3 + .... + n-1 + n = n(n+1)/2
j=1
n
Σ 2^j = 2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n+1) - 1
j=0
The above summation is the decimal value of a binary number with n+1 bits all
flipped on.
Double Summation. (works like a nested for loop)
3 2
Σ Σ i + j = (1+1) + (1+2) + (2+1) + (2+2) + (3+1) + (3+2) = 21
i=1 j=1
Some summation rules.
n n
Σ ci = c Σ i
i=1 i=1
n n n
Σ i + ci^2 = Σ i + c Σ i^2
i=1 i=1 i=1
n n 4
Σ i = Σ i - Σ i
i=5 i=1 i=1
n n-1
Σ i = Σ i + n
i=1 i=1
n n 49
Σ i = Σ i - Σ i
i=50 i=1 1
Set Cardinality and Countability.
Def: Given sets A and B, |A| = |B| if there is a bijection f: A->B.
If A = {1,2,...,n}, |A| = n (finite)
N = {0,1,2,3,4,....}, and |N| = infinite (also denoted by little-omega)
Z+ = {1,2,3,4,....}, and |Z+| = infinite
Countability.
Def: A set S is countable if it is finite or has the same cardinality of
N. A set has the same cardinality of N if there is a bijection from N or
Z+ to S.
Show that there is a bijection from Z+ -> Q, where Q is the set of positive
rational numbers. A number is rational if there are 2 positive integers p,q
such that x = p/q.
The following infinite matrix contains all possible rational numbers:
1/1 2/1 3/1 4/1 5/1 6/1 7/1 ...
1/2 2/2 3/2 4/2 5/2 6/2 7/2 ...
1/3 2/3 3/3 4/3 5/3 6/3 7/3 ...
1/4 2/4 3/4 4/4 5/4 6/4 7/4 ...
.
.
.
Map Z+ to the rational numbers in this matrix following this pattern:
1 2 3 4 5 6 7 ...
1/1 1/2 2/1 3/1 2/2 1/3 1/4 ...
All rational numbers will be hit in order. qed.