Lecture 20 Sequences and Summations
Lecture 25 Recurrence Relation
Goals and Objectives:
• Understand recurrence relation and how to use it to count
• Understand the solution of recurrence relation
Read 6.1, p. 401 – 408, 6.2, p. 413 – 416
Problem: How many bit strings of length of 10 that do not have 2 consecutive 0's?
Recurrence Relation
Definition. A recurrence relation of a sequence {an }, n=1,2,... is an
equation expressing an in terms of an-1 , an-2 , ..., a1 (or a0 )
A sequence is a solution of the relation if all terms satisfy the
equation. If initial conditions are given, then the solution is unique.
Example.
Given a recurrence relation an = an-1 + an-2 , n=2,3,...
The sequence {3,4,7,11,18,...} is a solution of the recurrence
relation.
The sequence {3,5,8,13,21,...} is another solution of the recurrence
relation.
If given initial conditions a0 =1, a1 =1 then the Fibonacci sequence
{1,1,2,3,5,8,13,21,...} is the solution of the recurrence relation.
Applications
The recurrence method can be used for counting when the problem can be defined recursively by divide-and–conquer.
A. Compound Interest
Examples.
(1) Suppose a person deposits $10,000 to a saving account that has APR
11% compounded annually. How much will it be after 30 years?
Ans.
Always set up the sequence nth term as the problem's answer ( in terms of n), i.e., an = the amount after nth years
Then
(i) set up recurrence relation
an = an-1 + 0.11* an-1 or
an = 1.11* an-1 , n=1,2,...
(ii) Give initial condition
a0 = 10,000
(iii) Solve the recurrence relation
a1 = 1.11* a0
a2 = 1.11* a1 = (1.11)2 a0
a3 = 1.11* a2 = 1.11(1.11*a1 ) = (1.11)2 a1 = (1.11)3 a0
...
an = (1.11) n a0 = (1.11) n *10,000 , n=0,1,2,...
Therefore
a30 = (1.11) 30 *10,000= 228,922.97
Solution of Recurrence Relation
Definition. A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form
an = c1an-1 + c2an-2 + … + ck an-k , n=k, k+1,...
where ck [pic]0, c1, c2, … , ck are constants.
Example.
a) The recurrence relation
an = 1.11* an-1 , n=1,2,...
is a linear homogeneous recurrence relation of degree 1.
b) The recurrence relation
an = an-1 + an-2 , n=2,3,...
is a linear homogeneous recurrence relation of degree 2.
Theorem. The solution of a linear homogeneous recurrence relation of degree 1
an = c1an-1 with initial condition a0 = [pic] and constant coefficient c1 is
an = [pic] * r 1 n , n=1,2,...
= a0 * c 1 n
where r1 satisfies the equation
x= c 1
Example.
Solve
an = 1.11* an-1 , n=1,2,...
where a0 = 10,000
Solution:
[pic]=10,000
c 1=1.11
an = [pic] * c 1 n = 10,000 (1.11) n
n=1,2,...
Theorem. The solution of a linear homogeneous recurrence relation of degree 2
an = c1an-1 + c2an-2 with initial condition a0 = [pic] + [pic], a1 = [pic] * r 1 + [pic] * r 2 and constant coefficient c1 and c2 is
an = [pic] * r 1 n + [pic] * r 2 n , n=1,2,...
where 2 different roots r 1 and r 2 satisfy the equation
x 2 = c1 x + c2
Example.
Solve the recurrence relation (Fibonacci numbers)
an = an-1 + an-2 , n=2,3,...
Solution:
c1 =1 and c2 =1
Solutions for
x 2 = x + 1
are r1 = (1+[pic])/2 and r2 = (1-[pic])/2
Initial conditions:
a0 = [pic] + [pic]= 0,
a1 = [pic] * r 1 + [pic] * r 2 = [pic] *(1+[pic])/2 + [pic] * (1-[pic])/2=1
After solving the 2 equations above, we have
[pic] = [pic]/5
[pic]= -[pic]/5
an = [pic]/5 * ((1+[pic])/2 ) n -[pic]/5 * ((1-[pic])/2 ) n , n=1,2,...
The above formula for nth Fibonacci number is called Binet’s formula.
Definition. The golden ratio [pic] is (1+[pic])/2
Definition. A rectangle such that the ratio of the length and width is [pic] is called a golden rectangle.
Lamé’s Theorem
1) If k [pic] 3 and Fk and Fk+1 are consecutive Fibonacci numbers, then Fk+1/Fk < 2.
2) If k [pic] 1 and Fk and Fk+1 are consecutive Fibonacci numbers, then gcd(Fk, Fk+1)=1.
3) If m and n are positive integers with m[pic] n, then the Euclidean Algorithm computes gcd(m,n) in no more than log(n) +1 steps (where log uses base [pic]).
4) If m and n are positive integers with m[pic] n, then the Euclidean Algorithm computes gcd(m,n) in no more than 5N steps, where N is the number of digits in the decimal expansion of n.
B. Tower of Hanoi
How many moves needed to move n disks of different sizes from one peg to another using an auxiliary peg?
Rule: move one disk at a time and smaller disk cannot be under larger
disk.
Ans:
an = # of moves for n disks from one peg to another
Then (i) set up recurrence relation
an = 2* an-1 + 1, n=2,...
(ii) Find initial condition
a1 = 1
(iii) Solve the recurrence relation
a2 = 2* a1 + 1
a3 = 2* a2 + 1 = 2*(2*a1 +1) +1= 22 a1 +2 +1
...
an = 2n-1 a1 + 2n-2 +... + 2 + 1 = 2n-1 + 2n-2 +... +2+1 = 2n - 1
(3) How many bit strings of length of 5 that do not have 2 consecutive
0's?
an = # of bit strings of length n that do not have 2 consecutive 0's
Then
(i) set up recurrence relation
Since an have either end with 1 or end with 10
Hence,
an = an-1 + an-2 , n=3,4,...
(ii) Find initial condition
a1 = 2
a2 = 3
(iii) Solve the recurrence relation
a3 = a2 + a1
a4 = a3 + a2 = 2 a2 + a1
a5 = a4 + a3 = 3 a2 + 2 a1 = 3*3+2*2 = 13
Another way to solve the problem: (without using recurrence relation)
Number of bit strings of length of 5 that do not have 2 consecutive 0's
= Total number of bit strings of length 5 -
number of bit strings of length 5 that have 2 consecutive 0's
5
= 2 - number of bit strings of length 5 that have 2 consecutive 0's
To find number of bit strings of length 5 that have 2 consecutive 0's we
have
Pattern Number
_______ ______
00 001{01}
10
11
1001{0}
1
{0}1001
1
{01}100
10
11
00100 11
000 0001{0}
1
10001
{11}000
01 5
0000 0000{1}
{1}0000 2
00000 00000 1
__________________________________
19
Therefore, Ans = 32-19=13
Assignment #21
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- lab 20 energy and photosynthesis
- 20 bath and body coupon
- 20 inventors and their inventions
- sequences and series practice problems
- sequences and series test pdf
- arithmetic sequences and series pdf
- october 20 holidays and observances
- unit 1 assignment sequences and series
- arithmetic sequences and series worksheet
- end of chapter 20 questions and answers
- august 20 holidays and observances
- arithmetic sequences and series