Fibonacci.dvi
The Fibonacci Sequence and Generalizations
Text Reference: Section 5.3, p. 325
The purpose of this set of exercises is to introduce you to the much-studied Fibonacci sequence,
which arises in number theory, applied mathematics, and biology. In the process you will see how
useful eigenvalues and eigenvectors can be in understanding the dynamics of difference equations.
The Fibonacci sequence is the sequence of numbers
0, 1, 1, 2, 3, 5, 8, 13, . . . .
You can probably see the pattern: Each number is the sum of the two numbers immediately pre-
ceding it; if yk is the kth number in the sequence (with y0 = 0), then how can y100 be found
without just computing the sequence term by term? The answer to this question involves matrix
multiplication and eigenvalues. The Fibonacci sequence is governed by the equation
yk+2 = yk+1 + yk,
or
yk+2 − yk+1 − yk = 0.
If you have studied Section 4.8, you will recognize the last equation as a second-order linear
difference equation. For reasons which will shortly become apparent, a trivial equation is added to
get the following system of equations:
yk+1 = yk+1
yk+2 = yk+1 + yk
To see how linear algebra applies to this problem, let
uk =
[
yk
yk+1
]
The above system of equations may then be written as
uk+1 = Auk
where
A =
[
0 1
1 1
]
To find yk, just look at the bottom entry in uk. The vector uk could be written in terms of u0 by
noting that
uk = Auk−1 = AAuk−2 = · · · = Aku0
The first goal is to find an easy way to compute Ak. This is where eigenvalues and eigenvectors
enter the picture.
1
Questions:
1. Using your technology, compute A5 and use it to find u5 and y5.
2. Show that the eigenvalues of A are
λ1 =
1 +
√
5
2
, λ2 =
1 −
√
5
2
by solving the characteristic equation of A.
3. Show that [
−λ2
1
]
and
[
−λ1
1
]
are eigenvectors of A corresponding to λ1 and λ2 respectively. You may find it helpful to
note λ1 + λ2 = 1 and λ1λ2 = −1.
4. Explain why A is diagonalizable.
5. Find (by hand) a matrix P and a diagonal matrix D for which A = PDP−1.
6. Use your technology to calculate D10, and use it to find A10, u10, and y10. Confirm your
result for y10 by writing out the Fibonacci sequence by hand.
7. A formula for yk may be derived using the following two questions. Use the above expres-
sions for P , D, and Ak to show that a general form for Ak is
Ak =
1√
5
[
λk2λ1 − λk1λ2 λ
k+1
2 λ1 − λ
k+1
1 λ2
λk1 − λk2 λ
k+1
1 − λ
k+1
2
]
8. Use the result of Question 7 to find uk and yk. Again make note of the fact that λ1λ2 = −1.
If you’ve worked it out all right, you should have found that
yk =
1
√
5
(
λk1 − λ
k
2
)
=
1
√
5
(
1 +
√
5
2
)k
−
(
1 −
√
5
2
)k
Calculate y10 using this formula, and compare your result to that of Question 6.
9. Notice that the second of the two terms in parentheses is less than 1 in absolute value, so as
higher and higher powers are taken, it will approach zero. The following equation results:
yk ≈
1
√
5
(
1 +
√
5
2
)k
Use this approximation to approximate yk+1/yk.
2
The approximation for yk+1/yk which you found in the last question is called the golden ratio, or
golden mean. The ancient Greek mathematicians thought that this ratio was the perfect proportion
for the rectangle. That it appears in such a “remote” area as the limiting ratio for the Fibonacci
sequence (which occurs in nature in sunflowers, nautilus shells, and in the branching behavior of
plants) makes one wonder about the connection between nature, beauty, and number.
The above work on the Fibonacci sequence can be generalized to discuss any difference equation
of the form
yk+2 = ayk+1 + byk,
where a and b can be any real numbers. A sequence derived from this equation is often called a
Lucas sequence.
Questions:
10. Consider the Lucas sequence generated by the difference equation
yk+2 = 3yk+1 − 2yk,
with y0 = 0 and y1 = 1. Write out by hand the first seven terms of this sequence and see if
you can find the pattern. Then repeat the above analysis on this sequence to find a formula
for yk.
11. Consider the Lucas sequence generated by the difference equation
yk+2 = 2yk+1 − yk,
with y0 = 0 and y1 = 1. Find the pattern by writing out as many terms in the sequence as
you need. Will an analysis like that for the Fibonacci sequence work in this case? Why or
why not?
3
copyright: An Addison-Wesley product. Copyright (c) 2003 Pearson Education, Inc.
text: You can also view this case study in the following formats:
Mathematica:
maple:
matlab: