Transcript Document

Lecture 8
2.4 Sequences and Summations
Sequences
A sequence is a function from a subset of the set of natural numbers N or non-negative integers Z*
to a set S. We use the notation sn to denote the image of the integer n. We call sn a term of the
sequence.
N
1,
2,
3, 4, 5, ...
S
s1, s2, s3, s4, s5, ...
Z* 0, 1, 2, 3, 4, ...
S
s0, s1, s2, s3, s4, ...
It is important to be able to express the sequence S in closed form as a function. For example,
S = { 1, 4, 9, 16, 25, ...} has a closed form sn = n2.
S = { 1, 1/2, 1/3, 1/4, ...} is sn = 1/n.
S = { 0, 4, 18, 48, 100, ...} is sn = ?
Special Integer Sequences
1, 1/2, 1/4, 1/8, . . .
1, 3, 5, 7, . . .
1, -1, 1, -1, . . .
0, 4, 18, 48, 100, . . .
2, 5, 10, 17, 26, 37, . . .
Example: Method of Finite Differences
candidate for a Computer Program
What is the next number in the sequence?
0
4
18
48
100
-
-
-
-
4
14
30
52
10
16
6
22
6
80
28
6
180
An Algebraic Solution
candidate for a Computer Program
N
1
2
3
4
5
6
S
2
5
10
17
26
37
3
5
2
7
2
9
2
11
2
Sn  C1 (n)  2  C2 (n)  5  C3 (n)  10

( n  2)(n  3)
( n  1)(n  3)
( n  1)(n  2)
2 
5 
 10
2
1
2
 (n 2  5n  6 )   5(n 2  4n  3)  5(n 2  3n  2)
Sn  n2  1
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. An arithmetic progression
is a discrete analogue of the linear function
f(x) = dx + a.
a
a+d
d
a+2d
d
a+3d
d
. . . a + nd
. . .
the difference between any successive pair of terms is equal to d
Geometric Progression
A geometric progression is a sequence of the form
a, ar, ar2, ... , arn
where the initial term a and the common ratio r are real numbers. A geometric progression is a
discrete analogue of the exponential function
f(x) = arx.
a
ar2
ar
. . .
ar(n-1) arn
arn
ar(n-1)
ar
a
ar2
ar
. . .
r
r
. . .
r
the ratio of any successive pair of terms is equal to r
Building a Pyramid
1

4

9

16
sn  n 2
n
1
5
14
30
 i2
i 1
1
13

5
25
...
 n 2

n
for
n

3



'
i

1
Sn   n

n2
2
2
 i   i otherwise
i 1

i 1
Summations
Summation notation below uses an integer variable i called the index of summation that runs
through all integers starting with its lower limit m and ending with its upper limit n. The value
of the term ai is computed for each i and added to the accumulating sum of all the terms
n
 ai
i m
Is is important to be able to express summations in closed forms as functions...
Geometric Series
The sum of terms of a geometric progression is called a geometric series. The closed form for a
geometric progression (when a and r are real and r is not zero),
 ar n1  a

i
if r  1
ar


 r 1
i 0
( n  1)a if r  1
n
These are two important special cases of the geometric series...
finite series
infinite series
Binomial Identities
n
n!
   C n, m 
m!( n  m)!
n
m
n
0
1
2
3
0
1
2
3
4
4
5
Pascal's Triangle
 n   n  1   n  1
 


 m   m  1  m 
Recurrence Relation
for Combinations
Power Series
These series are used in calculators and computer CPU's to compute exponential and
trigonometric functions. While the proofs of these formulae are the primary concern for
mathematics, their computational complexity and the possibility of improving their efficiency
are the primary concern in computer science...
Exponential
Trigonometric
Cardinality
The sets A and B have the same cardinality if and only if there is a one-to-one correspondence
from A to B.
Note: It is not a requirement that the one-to-one correspondence be known or provable, just that it
exists. For more info on the continuing controversy regarding unprovable theorems in discrete
mathematics, search on Cantor's Diagonalization Theorem, large cardinal axiom, Borel
Diagonalization Theorem, and Axiom of Choice. For example see,
http://www.algebra.com/algebra/about/history/Talk:Axiom-of-choice.wikipedia
A set that is either finite or has the same cardinality as the set of positive integers is called
countable. A set that is not countable is called uncountable.
1
2
3
4
5
6
7
8
9 10 11 12 ...
1
3
5
7
9 11 13 15 17 19 21 23 ...
Rational Numbers are Countable
There is a one-to-one correspondence between the natural numbers and the rational numbers
(assuming that n/m and qn/qm are considered to be different rational numbers.
1
1
2
1
3
1
4
1
...
1
2
2
2
3
2
4
2
...
1
3
2
3
3
3
4
3
...
1
4

2
4

3
4

4
4

...
Cantor's Diagonalization "Proof"
Cantor's proof requires the axiom of choice in which we assume that we can choose a value from
a list in order to prove that the list does not exist.
We wish to prove that the real numbers between 0.0 and 1.0 are not countable. We first assume
that there is a one-to-one correspondence between the natural numbers and the reals in the
interval (0.0,1.0) as shown below.
N
reals in (0.0, 1.0)
1
0.d11 d12 d13 d14 ...
2
0.d21 d22 d23 d24 ...
3
0.d31 d32 d33 d34 ...
4
0.d41 d42 d43 d44 ...
:
:
where dij is the jth digit of the real number corresponding to the ith natural number. From this list
we construct a number,
0.c1 c2 c3 c4 ...
where, ci = (dii +1) mod 10. This number clearly lies in the interval (0.0, 1.0) but is not a member
of the list above since its ith digit is different from the ith digit of the ith number for every number
in the list.
Problems for Cantor's Proof
First of all this proof is not just a proof by contradiction. It has the additional requirement that in
order to prove the contraction there must exist an entity which cannot exist if the proof is valid.
This is fundamentally different from demonstrating that if a statement S is true then a contradiction
exists, which means that S must be false. In the case of Cantor's Proof we assume that the set of reals
can be arranged into a list that contains all the members of the list. Then we assume that a value can
be composed from the members of the list creating a new member in the set that is not in the list.
Only if this impossible value exists can we prove that the list does not exist and, by extension the new
member also cannot exist. This is one step removed from proof-by-contradiction and therefore
requires an additional assumption (i.e. another axiom called the Axiom of Choice).*
0.4309411290814208725430924309842109...
0.7916109102982160219176902431932789...
0.2191190110012291029671642048275386...
0.1239010101902748657329873280783217...
0.4999999999999999999999999999999999...
there is no well-ordering
of the reals in this set...
In this example the composite number is 0.499999... But we must assume that there are infinitely
many numbers in the list that do not contain any 9's therefore 0.4 followed by all 9's could not be
the composite number. Since there is nothing special about the use of 9's in this example, we can
make a similar argument about any particular composite number (refuting the axiom of choice), and
therefore we cannot generate a value not in the list... Which means that we cannot prove anything
about the countability of the set of reals in the interval (0.0, 1.0) using this method.
*http://www.recipeland.com/encyclopaedia/index.php/Axiom_of_choice
Double Summations
4
3
S    3ij
i 1 j 1
4
3
S    3ij
i 1 j 1
4
with ada.integer_text_io;
use ada.integer_text_io;
procedure double_sum_demo is
S : integer := 0;
begin
for i in 1..4 loop
for j in 1..3 loop
S := S + 3*i*j;
end loop;
end loop;
put(S,0);
end double_sum_demo;
  3i  6 i  9i
i 1
4
  18i
i 1
 18  36  54  72
 180
Some Useful Summation Formulae
A Numeric Example
Queuing Theory
Candidate for a Computer Program
Customers arrive randomly but at an average rate of l customers per unit time. A server provides
service at at rate of m customers per unit time. If m>l then this system will reach a steady state.
We will define the state of this system by the number of customers in the system. An empty system
(no customers) is in state S0. When there is one customer the system is in state S1 and so on. In the
steady state the rate at which customers enter the system is equal to the rate at which they leave the
system.
Obtaining a Closed-Form Solution
by repeated substitution of Eq n into Eq n-1
since the system must be in some state the sum
of all probabilities must equal 1
l/m is strictly less than 1 so the closed form for
the infinite series applies
the average number of customers in the system
again we apply the closed form
the average time a customer spends in the system