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.

Google Online Preview   Download