52 CHAPTER 1 Sets, Proof Templates, and Induction
The Fibonacci numbers were defined by Leonardo of Pisa, filius (son of) Bonacci,
who lived around 1200. Leonardo developed the sequence in predicting the size of
a population of rabbits. F, is the number of pairs of rabbits he predicted one would
have n months after buying a pair of baby rabbits under the assumption that a pair of
rabbits matured in one month and produced a pair of offspring each month thereafter.
Month (n) Old Pairs New Pairs F.
(^0) I
2 4 2
3
4
5
Furthermore, he assumed that the rabbits always produced a male and a female as
each pair of offspring. So, Fo = 1 for the pair just purchased. F 1 = 1, because after
one month, the original pair has just matured and are only now ready to start breeding.
F 2 = 2, because the original pair has just had one pair of offspring. F 3 = 3, because
the original pair has had another pair of offspring and the first offspring have just
matured and are only now ready to start breeding. What happens during month n?
All the rabbits alive during month n - 1 are still alive. In addition, all the rabbits alive
during month n - 2 have matured, and each pair has had one pair of offspring. Hence,
Fn = Fn-1 + Fn-2.
Example 4. Show that the identity F 1 + F 3 + F 5 + .. + F 2 n- 1 = F 2 n - 1 is true for
all n > 1.
Solution. Let no = 1. Prove the identity by induction on n. Let
T={nEN:n> landFl+F 3 +...+F 2 n- 1 =F 2 n-1}
Prove that T = {n E N : n > 11.
(Base step) Prove the result for n = 1. The left-hand side in this case is just the sum
of all the Fibonacci numbers starting with F 1 and ending with F( 2 .I-1). There is just one
such Fibonacci number, F 1 , and the value of the left-hand side is 1. The right-hand side is
F 2. 1 - 1 = F 2 - 1 = 2 - 1 = 1. So, the two sides are equal, and 1 E T.