CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 115
EXAMPLE 6.11 Consider the celebrated Fibonacci sequence:
an=an− 1 +an− 2 , with a 0 = 0 ,a 1 = 1The first 10 terms of the sequence follow:
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ,...
Sometimes the Fibonacci sequence is defined using the initial conditionsa 0 =1,a 1 =1 or the initial conditions
a 1 =1,a 2 =2. We usea 0 =0,a 1 =1 for computational convenience. (All three initial conditions yield the
same sequence after the pair of terms 1, 2.)
Observe that the Fibonacci sequence is a homogeneous linear second-order recurrence relation, so it can be
solved using Theorem 6.8. Its characteristic polynomial follows:
(x)=x^2 −x− 1Using the quadratic formula, we obtain the roots:
r 1 =1 +√
5
2,r 2 =1 −√
5
2By Theorem 6.8, we obtain the general solution:
an=c 1(
1 +√
5
2)n
+c 2(
1 −√
5
2)nThe initial conditions yield the following system of two linear equations inc 1 andc 2
Forn=0 anda 0 = 0 ,we get: 0 =c 1 +c 2Forn=1 anda 1 = 1 ,we get: 1 =c 1(
1 +√
5
2)
+c 2(
1 −√
5
2)The solution of the system follows:
c 1 =1
√
5,c 2 =−1
√
5
Accordingly, the following is the solution of the Fibonacci recurrence relation:
an=1
√
5(
1 +√
5
2)n
−1
√
5(
1 −√
5
2)nOne can show that the absolute value of the above second term foranis always less than 1/2. Thusanis also the
closest integer to the number
1
√
5(
1 +√
5
2)n
≈( 0. 4472 )( 1. 6180 )nSolution when Roots of the Characteristic Polynomial are Equal
Suppose the roots of the characteristic polynomial are not distinct. Then we have the following result.Theorem 6.9: Suppose the characteristic polynomial(x)=x^2 −sx−tof the recurrence relation
an=san− 1 +tan− 2
has only one rootr 0. Then the general solution of the recurrence relation follows, wherec 1 and
c 2 are arbitrary constants:an=c 1 r 0 n+c 2 nrn 0The constantsc 1 andc 2 may be uniquely computed using initial conditions.