160
Recursion, Recurrence Relations, and Analysis of Algorithms
Other mathematical properties of the Fibonacci sequence are given in
Example 3 and in the exercises at the end of this section. But it’s not only
mathematicians who are interested in the Fibonacci sequence. Fibonacci numbers often occur in nature. The number of petals on a daisy is often a Fibonacci
number. Viewing a pine cone from its base, the seeds appear to be arranged in
clockwise and counterclockwise spirals. Counting the number of each kind of
spiral often gives two consecutive Fibonacci numbers (here 8 and 13). The same is
true for seeds in flowers such as sunflowers, or for spirals on pineapples.
And in the worlds of art and architecture, the golden ratio is thought to create
aesthetically pleasing proportions. The golden ratio is
1 + "5
2
≈ 1.6180339
and is the value approached by the ratio of two consecutive Fibonacci numbers
F(n + 1)/F(n) for larger and larger values of n.
example 3
Prove that in the Fibonacci sequence
F(n + 4) = 3F(n + 2) − F(n) for all n ≥ 1
Because we want to prove something true for all n ≥ 1, it is natural to think
of a proof by induction. And because the value of F(n) depends on both F(n − 1)
and F(n − 2), the second principle of induction should be used. For the basis step
of the inductive proof, we’ll prove two cases, n = 1 and n = 2. For n = 1, by substituting 1 for n in the equation we want to prove, we get
F(5) = 3F(3) − F(1)
or (using values computed in Practice 2)
5 = 3(2) − 1
which is true. For n = 2,
F(6) = 3F(4) − F(2)
or
8 = 3(3) − 1
which is also true. Assume that for all r, 1 ≤ r ≤ k,
F(r + 4) = 3F(r + 2) − F(r).
1
2
3
5
6
7
8
4
1
2
3
5
6
7
8
9
10
11
12
13
4