Chapter 0: Section 0.1 - Part 1

1.  "It is not difficult to find a formula for $F_n$"

(1)  The standard recurrence relation for Fibonnaci number $n$ is:

• $F_0 = 0$
• $F_1 = 1$
• For $n \ge 2$

$$F_n = F_{n-1} + F_{n-2}$$

(2)  The formula for $n$ is as follows:

$$F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$

Notes:

•   The formula is known as Binet's Formula and its derivation showcases the deep relationship between the Fibonacci number and the golden ratio.

• The derivation and elementary proofs are detailed here.

Exercises:

1.  Exercise 0.1.1:  (a)  Use the recurrence relation for the fibonacci numbers, and induction to prove that every Fibonacci number is an integer.

Solution:

• S(1) is true since $F_1 = 1$ is an integer.
• We assume that S(k) is true, that is, S(k) is an integer.
• S(k+1) = S(k) + S(k-1) which is an integer since the sum of two integers is an integer by the closure property on addition.  See here for properties of integers.

2.  Exercise 0.1.1: (b) Prove that Binet's Formula is correct by verifying that it holds for $n = 0, 1$ and then, for all larger integers $n$ by induction.

Solution:

• S(0) is true since $F_0 = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^0 - \left(\frac{1-\sqrt{5}}{2}\right)^0\right) = 0$
• S(1) is true since $F_1 = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^1 - \left(\frac{1-\sqrt{5}}{2}\right)^1\right)  = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}-1+\sqrt{5}}{2}\right) = 1$
• We assume that S(k) is true, that is, $F_k = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^k - \left(\frac{1-\sqrt{5}}{2}\right)^k\right)$
• S(k+1) is true since $F_{k+1} = F_k + F_{k-1} = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^k - \left(\frac{1-\sqrt{5}}{2}\right)^k\right) + \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{k-1} - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\right)$ 
• $= \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^k - \left(\frac{1-\sqrt{5}}{2}\right)^k + \left(\frac{1+\sqrt{5}}{2}\right)^{k-1} - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\right)$ 
• $= \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(\frac{1+\sqrt{5}}{2} + 1\right) - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(\frac{1-\sqrt{5}}{2}+1\right)\right)$ 
• $=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(\frac{3+\sqrt{5}}{2}\right) - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(\frac{3-\sqrt{5}}{2}\right)\right)$
• $=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(\frac{1+\sqrt{5}}{2}\right)^2 - \left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(\frac{1-\sqrt{5}}{2}\right)^2\right)$
• $=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{k+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{k+1}\right)$

3.  Exercise 0.1.2: Use induction on $n \ge 1$ to prove that (a) $F_1 + F_3 + \dots + F_{2n-1} = F_{2n}$

Solution:

• S(1) is true since $F_1 = 1 = F_2 = F_{2(1)}$
• We assume that S(k) is true, that is, $F_1 + F_3 + \dots + F_{2n-1} = F_{2n}$
• $F_{2n+2} = F_{2n+1} + F_{2n} = F_{2n+1} + F_{2n-1} + \dots + F_3 + F_1$

4.  Exercise 0.1.2:  Use induction on $n \ge 1$ to prove that (b) $1 + F_2 + F_4 + \dots + F_{2n} = F_{2n+1}$

Solution:

• S(1) is true since $1 + F_2 = 1 + 1 = 2 = F_1 + F2 = F3$
• We assume that S(k) is true, that is,  $1 + F_2 + F_4 + \dots + F_{2n} = F_{2n+1}$
• $F_{2n+3} = F_{2n+2} + F_{2n+1} = F_{2n+2} + F_{2n} + \dots + F_4 + F_2 + 1$

5.  Exercise 0.1.3: The number $\phi = \frac{1+\sqrt{5}}{2}$ is called the golden ratio.  (a) Prove that $\phi^2 = \phi + 1$

Solution:

• $\phi^2 = \left(\frac{1+\sqrt{5}}{2}\right)^2 = \frac{3+\sqrt{5}}{2} = \frac{1+\sqrt{5}}{2} + 1$

6.  Exercise 0.1.3: (b) Prove that $\phi^n = F_n\phi + F_{n-1}$ for all integers $n \ge 1$, by induction

Solution:

• S(1) is true since $\phi^1 = \frac{1+\sqrt{5}}{2} = F_1\phi + F_0$
• We assume that S(k) is true, that is, $\phi^n = F_n\phi + F_{n-1}$ for all integers $n \ge 1$
• $\phi^{n+1} = \phi\phi^n = \phi\left(F_n\phi + F_{n-1}\right) = F_n\phi^2 + F_{n-1}\phi = F_n\left(F_2\phi + F_1\right) + F_{n-1}\phi = F_n\phi + F_n + F_{n-1}\phi$
• $= F_{n+1}\phi + F_n$