Discrete Mathematics for Computer Science

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.