21.3. Linear Recurrences 877
Similarly, the second boundary condition implies that
f.1/Ds1 C
p
5
2! 1
Ct1
p
5
2! 1
D1:
Now we have two linear equations in two unknowns. The system is not degenerate,
so there is a unique solution:
sD1
p
51 C
p
5
2
tD 1
p
51
p
5
2:
These values ofsandtidentify a solution to the Fibonacci recurrence that also
satisfies the boundary conditions:
f.n/D1
p
51 C
p
5
21 C
p
5
2!n
1
p
51
p
5
21
p
5
2!nD
1
p
51 C
p
5
2!nC 1
1
p
51
p
5
2!nC 1
:It is easy to see why no one stumbled across this solution for almost six centuries.
All Fibonacci numbers are integers, but this expression is full of square roots of
five! Amazingly, the square roots always cancel out. This expression really does
give the Fibonacci numbers if we plug innD0;1;2, etc.
This closed form for Fibonacci numbers is known as Binet’s formula and has
some interesting corollaries. The first term tends to infinity because the base of
the exponential,.1C
p
5/=2D1:618:::is greater than one. This value is often
denoted and called the “golden ratio.” The second term tends to zero, because
.1
p
5/=2D 0:618033988:::has absolute value less than 1. This implies that
thenth Fibonacci number is:
f.n/D nC^1
p
5Co.1/:Remarkably, this expression involving irrational numbers is actually very close to
an integer for all largen—namely, a Fibonacci number! For example:
^20
p
5D6765:000029f.19/:This also implies that the ratio of consecutive Fibonacci numbers rapidly approaches
the golden ratio. For example:
f.20/
f.19/