## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required