Fibonacci Recurrence Relation
563
possibility can be determined. For example, it may be possible to determine whether such
a function can even be a solution:
a. - an-1 - an-2 = 0
Cn -2Cn-1
-2Cn-2
= o
cn-2 (C -- C -- 1) = 0
Since the product of two real numbers-namely, C02 and c
2 - c - 1-is zero, either
Cn-2 =0 or c
2 -c1 =0. If Cn-2 =0, then c=Oand an =Ofor alln > 0. This solution, called the zero function, is the trivial solution of the recurrence relation. For a
homogeneous recurrence relation, the zero function is always a solution. Since the primary
interest is in nontrivial solutions, suppose c A 0, which implies that c
2 - c - 1 = 0. This
equation is called the characteristic equation of the recurrence relation. The roots of this
equation are
C -2
2
This discussion began by asking if the nontrivial solutions of a second-order homogeneous recurrence relation have a form similar to the nontrivial solution of a firstorder homogeneous recurrence relation. By trying such a function, we found that if a
second-order homogeneous recurrence relation had such a nontrivial solution, then the
two possible constants that had the property were the solutions to the characteristic equation of the recurrence relation. Now, we prove that not only these two functions but also
any linear combination of two such functions are solutions of the recurrence relation. Much
like the previous discussion of back substitution, a conjecture about the form of a solution
has been found, and we must now prove that such functions really are solutions. It is beyond the scope of this text to prove the fundamental result that no other nontrivial solutions
of a second-order homogeneous recurrence relation exist. We will therefore just state the
result.
Theorem 1. Let a, = klan-1 ± k2an-2 for n > 2. Suppose the characteristic equation of this recurrence relation has distinct roots cl and c2. Any function of the form
H(n) = Acln + Bc 2 n, where A and B are arbitrary constants, is a solution of this recurrence relation.
Proof. To verify that a function of the form H(n) is a solution, write with all terms on the
left-side of the equal sign and then substitute H (n) for some value of n into the recurrence
relation, giving
an - klan-1 - k2an-2 =
H(n) - k1H(n - 1) - k 2 H(n - 2) =
Ac
B
+ BC
k
+ Bc')
- k 2 (Acn2 + Bcn2 ) =
a(c' -
c
- kn-2) + B(cn - kcj1 - kn-2) =
-1kc
2
-
kzc 2 2
Acn-2 (c2 -- klCl -- k2) -+- Bcn-2(c2 - klC2 - k2)
563
possibility can be determined. For example, it may be possible to determine whether such
a function can even be a solution:
a. - an-1 - an-2 = 0
Cn -2Cn-1
-2Cn-2
= o
cn-2 (C -- C -- 1) = 0
Since the product of two real numbers-namely, C02 and c
2 - c - 1-is zero, either
Cn-2 =0 or c
2 -c1 =0. If Cn-2 =0, then c=Oand an =Ofor alln > 0. This solution, called the zero function, is the trivial solution of the recurrence relation. For a
homogeneous recurrence relation, the zero function is always a solution. Since the primary
interest is in nontrivial solutions, suppose c A 0, which implies that c
2 - c - 1 = 0. This
equation is called the characteristic equation of the recurrence relation. The roots of this
equation are
C -2
2
This discussion began by asking if the nontrivial solutions of a second-order homogeneous recurrence relation have a form similar to the nontrivial solution of a firstorder homogeneous recurrence relation. By trying such a function, we found that if a
second-order homogeneous recurrence relation had such a nontrivial solution, then the
two possible constants that had the property were the solutions to the characteristic equation of the recurrence relation. Now, we prove that not only these two functions but also
any linear combination of two such functions are solutions of the recurrence relation. Much
like the previous discussion of back substitution, a conjecture about the form of a solution
has been found, and we must now prove that such functions really are solutions. It is beyond the scope of this text to prove the fundamental result that no other nontrivial solutions
of a second-order homogeneous recurrence relation exist. We will therefore just state the
result.
Theorem 1. Let a, = klan-1 ± k2an-2 for n > 2. Suppose the characteristic equation of this recurrence relation has distinct roots cl and c2. Any function of the form
H(n) = Acln + Bc 2 n, where A and B are arbitrary constants, is a solution of this recurrence relation.
Proof. To verify that a function of the form H(n) is a solution, write with all terms on the
left-side of the equal sign and then substitute H (n) for some value of n into the recurrence
relation, giving
an - klan-1 - k2an-2 =
H(n) - k1H(n - 1) - k 2 H(n - 2) =
Ac
B
+ BC
k
+ Bc')
- k 2 (Acn2 + Bcn2 ) =
a(c' -
c
- kn-2) + B(cn - kcj1 - kn-2) =
-1kc
2
-
kzc 2 2
Acn-2 (c2 -- klCl -- k2) -+- Bcn-2(c2 - klC2 - k2)