Section 3.1 Recursive Definitions
175
can be yellow), n ≥ 1. The first four values are 2, 3, 5, 8, which—so far—form a subsequence of the
Fibonacci sequence. For example, D(3) = 5 because a three-story building can be painted
Y
Y
Y
B
B
Y
Y
B
Y
Y
Y
B
Y
B
Y
(Hint: think about a recursive expression for D(n + 1).)
37 a. The original problem posed by Fibonacci concerned pairs of rabbits. Two rabbits do not breed until
they are 2 months old. After that, each pair of rabbits produces a new pair each month. No rabbits ever
die. Let R(n) denote the number of rabbit pairs at the end of n months if you start with a single rabbit
pair. Show that R(n) is the Fibonacci sequence.
b. Write 27 and 62 as the sum of distinct nonconsecutive Fibonacci numbers.
38. a. The sequence of Catalan numbers is defined recursively by
C(0) = 1
C(1) = 1
C(n) = ∙
n
k=1
C(k − 1)C(n − k) for n ≥ 2
Compute the values of C(2), C(3), and C(4) using this recurrence relation.
b. Frank and Jody are both candidates for president of the County Council. The number of votes cast equals
2n, where n votes are cast for Frank and n for Jody. Votes are counted sequentially. The ballot problem
asks: In how many ways can the votes be counted so that Jody’s total is never ahead of Frank’s total?
The answer, as it turns out, is C(n), the nth Catalan number. For example, if n = 5, one possible counting
sequence that meets this requirement is
FFJJFJFFJJ
Using n = 3, write down all the satisfactory counting sequences and compare the result to the Catalan
number C(3).
39. A sequence is recursively defined by
S(1) = 2
S(2) = 2
S(3) = 6
S(n) = 3S(n − 3) for n ≥ 3
Prove that S(n) is an even number for n ≥ 1.
40. A sequence is recursively defined by
T(5) = 6
T(6) = 10
T(n) = 2T(n − 2) + 2 for n ≥ 7
Prove that T(n) ≥ 2n for n ≥ 7.