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 , 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 . Now we consider what happens for n = k + 1. In this case, we see that so the truth of the statement at n = k

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

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