O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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 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

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

Start Free Trial

No credit card required