# Book of Proof: Chapter 10, Exercise 30 Proof of Binet's formula [duplicate]

I am trying to solve this below problem from Hammack's Book of Proof.

Here $$F_n$$ is the $$n$$th Fibonacci number. Prove that $$F_n = \frac{\left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n}{\sqrt{5}}.$$

The formula for the Fibonacci numbers I have is: $$F_1 = 1$$, $$F_2 = 1$$, and $$F_n = F_{n-1} + F_{n-2}$$ for $$n \geq 3$$. My first point of confusion is exactly how many base cases I have access to. I want to prove the $$n+1$$ case after having proved the $$n$$ case, but I really want both $$n$$ and $$n+1$$ to have this recursive formula, which suggests to me that I need to prove, manually, the $$n=1$$, $$n=2$$, and $$n=3$$ cases. From there, it's just a matter of assuming it for $$n$$ and brute-forcing the $$n+1$$ case.

Is that correct? This is really my only point of confusion. I can work out the computation.

• You can check for $n=1$ and $n=2$ and then prove that the formula is still valid for $F_{n+2}$ knowing that $F_{n+1}$ and $F_n$ are given by your formula. Sep 7, 2021 at 19:13
• Ok, so proving $n=1$ and $n=2$ allows me to assume the result for $n \geq 2$ and then use the recursive formula for $F_{n+1}$ because $n+1 \geq 3$. Is that the idea? Sep 7, 2021 at 19:15
• "Ok, so proving 𝑛=1 and 𝑛=2 allows me to assume the result for 𝑛≥2" Not at all. It allows you show that the result for one value of n ≥ 2 implies the result for n+1. That would suffice to prove the general statement by induction. Sep 7, 2021 at 19:20
• You will prove that $F_{n+2}=\frac{\left(\frac{1 + \sqrt{5}}{2} \right)^{n+2} - \left(\frac{1 - \sqrt{5}}{2} \right)^{n+2}}{\sqrt{5}}$ knowing that $F_{n+1}=\frac{\left(\frac{1 + \sqrt{5}}{2} \right)^{n+1} - \left(\frac{1 - \sqrt{5}}{2} \right)^{n+1}}{\sqrt{5}}$ and $F_{n}=\frac{\left(\frac{1 + \sqrt{5}}{2} \right)^{n} - \left(\frac{1 - \sqrt{5}}{2} \right)^{n}}{\sqrt{5}}$ as you will use $F_{n+1}$ AND $F_n$ you need to initialize with $n=1$ AND $n=2$. Sep 7, 2021 at 19:22
• consider $\phi^2=\phi+1$ Sep 7, 2021 at 19:31

$$F_0 = 0, F_1 = 1, F_{n} = F_{n-1} + F_{n-2}$$

$$\frac{1 + \sqrt {5}}{2},\frac {1 - \sqrt {5}}{2}$$ are roots of the polynomial $$x^2 - x - 1 = 0$$

Rearranging we get $$x^2 = x + 1$$

Claim: $$(\frac {1+\sqrt 5}{2})^n = F_{n-1} + F_{n}(\frac {1+\sqrt 5}{2})$$

Proof by induction:

Base case n = 1
$$(\frac {1+\sqrt 5}{2})^1 = 0 + F_1(\frac {1+\sqrt 5}{2})$$

Suppose $$(\frac {1+\sqrt 5}{2})^n = F_{n-1} + F_{n}(\frac {1+\sqrt 5}{2})$$

We must show that $$(\frac {1+\sqrt 5}{2})^{n+1} = F_{n} + F_{n+1} (\frac {1+\sqrt 5}{2})$$ basd on the hypothesis.

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

Do the same for $$(\frac {1-\sqrt 5}{2})^n = F_{n-1} + F_n(\frac {1-\sqrt 5}{2}).$$

Then
$$\frac {(\frac {1+\sqrt 5}{2})^n - (\frac {1-\sqrt 5}{2})^n}{(\frac {1+\sqrt 5}{2}) - (\frac {1-\sqrt 5}{2})}\\ \frac {(F_{n-1} + F_n(\frac {1+\sqrt 5}{2})) - (F_{n-1} + F_n(\frac {1-\sqrt 5}{2}))}{(\frac {1+\sqrt 5}{2}) - (\frac {1-\sqrt 5}{2})}\\ \frac {F_n(\frac {1+\sqrt 5}{2}) - F_n(\frac {1-\sqrt 5}{2})}{(\frac {1+\sqrt 5}{2}) - (\frac {1-\sqrt 5}{2})}\\ F_n$$