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 (F_{r}, F_{r+2}) > 1 . But gcd (F_{r−1}, F_{r+1}) = 1. Consequently, there exists a positive integer d, where d > 1 and d divides both F_{r} and F_{r+2}. Since F_{r+2} = F_{r+1} + F_{r}, it follows that d divides F_{r+1}. But this contradicts gcd (F_{r}, F_{r+1}) = 1, the result in Property 4.1.

3. Proof: F_{2(n+1)} = F_{2n+2} = F_{2n+1} + F_{2n} = (F_{2n} + F_{2n−1}) + F_{2n} = 2F_{2n} + F_{2n−1.}

5. Proof: Simply add F_{n} to each side of the result in Exercise 4.

7. Proof: F_{3n} = F_{3n−1} + F_{3n−2} = (F_{3n−2} + F_{3n−3}) + (F_{3n−3} + F_{3n−4}) = F_{3n−2} + 2F_{3n−3} + F_{3n−4} = (F_{3n−3} + F_{3n−4}) + 2F_{3n−3} + F_{3n−4} = 3F_{3n−3} + 2F_{3n−4} = 3F_{3n−3} + 2(F_{3n−3} + F_{3n−5}) = 3035F_{3n−3} − 2F_{3n−5} = 4F_{3n−3} + (F_{3n−4} + F_{3n−5}) − 2F_{3n−5} = 4F_{3n−3} + (F_{3n−5} + F_{3n−6} + F_{3n−5}) − 2F_{3n−5} = 4F_{3n−3} + F_{3n−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