174
Recursion, Recurrence Relations, and Analysis of Algorithms
31. The values p and q are defined as follows:
p =
1 + "5
2
and q =
1 − "5
2
a. Prove that 1 + p = p
2
and 1 + q = q
2
.
b. Prove that
F(n) =
p
n
− q
n
p − q
c. Use part (b) to prove that
F(n) =
"5
5
a
1 + "5
2
b
n
−
"5
5
a
1 − "5
2
b
n
is a closed-form solution for the Fibonacci sequence.
32. The Lucas sequence is defined by
L(1) = 1
L(2) = 3
L(n) = L(n − 1) + L(n − 2) for n ≥ 2
a. Write the first five terms of the sequence.
b. Prove that L(n) = F(n + 1) + F(n − 1) for n ≥ 2 where F is the Fibonacci sequence.
For Exercises 33–36, decide whether the sequences described are subsequences of the Fibonacci sequence, that
is, whether their members are some or all of the members, in the right order, of the Fibonacci sequence.
3
33. The sequence A(n), where A(n) = 1 + (the sum of the first n terms of the Fibonacci sequence), n ≥ 1. The
first four values are 2, 3, 5, 8, which—so far—form a subsequence of the Fibonacci sequence.
34. The sequence B(n), where B(n) = (n − 1)2
n−2
+ 1, n ≥ 1. The first four values are 1, 2, 5, 13, which—so
far—form a subsequence of the Fibonacci sequence.
35. The sequence C(n), where C(n) is the number of ways in which n coins can be arranged in horizontal rows
with all the coins in each row touching and every coin above the bottom row touching two coins in the row
below it, n ≥ 1. The first five values are 1, 1, 2, 3, 5, which—so far—form a subsequence of the Fibonacci
sequence.
n = 1
n = 2
n = 3
n = 5
n = 4
36. The sequence D(n), where D(n) describes the number of ways to paint the floors on an n-story building
where each floor is painted yellow or blue and no two adjacent floors can be blue (although adjacent floors
3 Exercises 33–36 are taken from “Mathematical Recreations” by Ian Stewart, Scientific American, May 1995.