Solutions for the Odd-Numbered Exercises

Part One: The Fibonacci Numbers

Exercises for Chapter 4

1. Proof: If not, there is a first integer r > 0 such that gcd (Fr, Fr+2) > 1 . But gcd (Fr−1, Fr+1) = 1. Consequently, there exists a positive integer d, where d > 1 and d divides both Fr and Fr+2. Since Fr+2 = Fr+1 + Fr, it follows that d divides Fr+1. But this contradicts gcd (Fr, Fr+1) = 1, the result in Property 4.1.

3. Proof: F2(n+1) = F2n+2 = F2n+1 + F2n = (F2n + F2n−1) + F2n = 2F2n + F2n−1.

5. Proof: Simply add Fn to each side of the result in Exercise 4.

7. Proof: F3n = F3n−1 + F3n−2 = (F3n−2 + F3n−3) + (F3n−3 + F3n−4) = F3n−2 + 2F3n−3 + F3n−4 = (F3n−3 + F3n−4) + 2F3n−3 + F3n−4 = 3F3n−3 + 2F3n−4 = 3F3n−3 + 2(F3n−3 + F3n−5) = 3035F3n−3 − 2F3n−5 = 4F3n−3 + (F3n−4 + F3n−5) − 2F3n−5 = 4F3n−3 + (F3n−5 + F3n−6 + F3n−5) − 2F3n−5 = 4F3n−3 + F3n−6.

9. Proof (By Mathematical Induction): We see that img, so the given statement holds in this first case. This provides the basis step of the proof. For the inductive step, we assume the truth of the result for n = k(≥ 0)—that is, that img. Now we consider what happens for n = k + 1. In this case, we see that

equation

so the truth of the statement at n = k

Get Fibonacci and Catalan Numbers: An Introduction now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.