# Fibonacci sequence, proof verification.

At the end of chapter $10$ of his "Book of Proof", Hammack calls for a proof of the Fibonacci sequence in a form that I did not encounter before, I would like to know if the proof that I give for it is correct.

• $30)$ 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}\,.$$

First, I can see the golden ratio in the equation, $$\frac {1+\sqrt 5}2 = \lim_{n\to \infty} \frac {F_{n+1}}{F_{n}} = \phi\,.$$

Then, I look at how $\frac {1-\sqrt 5}2$ relates to $\phi$, $$\frac 1\phi = \frac 2{1+\sqrt 5} = \frac {2(1-\sqrt 5)}{1-5} = -\frac{1-\sqrt5}2\,.$$

Using this in the given formula for $F_n$ gives,

$$F_n = \frac 1{\sqrt 5}\left(\phi^n - \left(-\frac 1\phi\right)^n\right)\,.$$

So I will use that as a simplification for my induction proof.

I start by making sure that $F_n$ holds for $n=1$ and $n=2$ such that the inductive step can be taken, $$F_1 = \frac 1{2 \sqrt 5}(1+\sqrt 5 -1 +\sqrt5) = \frac{2\sqrt 5}{2\sqrt5} = 1$$ $$F_2 = \frac 1{4 \sqrt 5}(1+2\sqrt 5+5 -1 +2\sqrt5 -5) = \frac{4\sqrt 5}{4\sqrt5} = 1$$ and I assume $F_{n} \,:\, n\in \Bbb Z^+$ is true.

We know that $F_n = F_{n-1}+F_{n-2}$ ergo,

\begin{align} F_{n}+F_{n-1} & = \frac 1{\sqrt 5}\left(\phi^{n} - \left(-\frac 1\phi\right)^{n}\right) + \frac 1{\sqrt 5}\left(\phi^{n-1} - \left(-\frac 1\phi\right)^{n-1}\right)\\ & = \frac 1{\sqrt 5}\left[\left(\phi^{n} + \phi^{n-1}\right) - \left(\left( -\frac 1\phi\right)^{n} + \left(-\frac 1\phi\right)^{n-1}\right)\right]\\ & \require{cancel}\cancel{= \frac 1{\sqrt 5}\left[\phi^{n}(1 + \frac 1\phi) - \left(1 - \phi\right)\left( -\frac 1\phi\right)^{n}\right]} \\ \end{align} $$\require{cancel}\cancel{1+\frac 1\phi = 1-\phi = \phi}$$ $$\require{cancel}\cancel{\therefore\quad F_{n}+F_{n-1} = \frac 1{\sqrt 5}\left(\phi^n - \left(-\frac 1\phi\right)^n\right) = F_{n+1}}$$

## Edit

Following the suggestions in the comments I edited the question and as suggested, I tried using the fact that $\phi$ and $-\frac{1}{\phi}$ are the roots of $x^2=x+1$ which I overlooked the first time.

So with that information in hand, I multiply $\phi^2 =\phi + 1$ by $\phi^{n-1}$ and $\left(-\frac 1\phi\right)^2 = \left(-\frac 1\phi\right) + 1$ by $\left(-\frac {1}\phi\right)^{n-1}$ as suggested to see,

$$\phi^{n+1} = \phi^n + \phi^{n-1}$$ $$\left(-\frac 1\phi\right)^{n+1} = \left(-\frac 1\phi\right)^n + \left(-\frac {1}\phi\right)^{n-1}$$

Then, knowing $F_1 =F_2 =1$ and assuming $F_{n} \,:\, n\in \Bbb Z^+$ is true, I use what I already found for $F_n+F_{n-1}$ and get,

\begin{align} F_{n}+F_{n-1} & = \frac 1{\sqrt 5}\left(\phi^{n} - \left(-\frac 1\phi\right)^{n}\right) + \frac 1{\sqrt 5}\left(\phi^{n-1} - \left(-\frac 1\phi\right)^{n-1}\right) \\ & = \frac 1{\sqrt 5}\left[\left(\phi^{n} + \phi^{n-1}\right) - \left(\left( -\frac 1\phi\right)^{n} + \left(-\frac 1\phi\right)^{n-1}\right)\right]\\ & = \frac 1{\sqrt 5}\left[\phi^{n+1} - \left(-\frac 1{\phi}\right)^{n+1}\right] = F_{n+1} \\ \end{align} $$\frac{F_{n}\implies F_{n+1}\;,\;F_{n}}{\therefore\;F_{n+1}}\qquad \text{modus ponens} \tag*{\blacksquare}$$

Is this proof correct and acceptable?

• You've got some errors and/or confusing bits in there. Here is something that you can use as an organizing principle: First, note that $(1\pm \sqrt 5)/2$ are the two roots of $x^2=x+1$, and multiply that polynomial by $x^{n-1}$ to show, e.g., that $\phi^{n+1}=\phi^n+\phi^{n-1}$. – Aaron Mar 23 '17 at 19:43
• In your displayed equation $${1\over\phi}=\cdots=-(-{1\over\phi})^n$$ everything is OK except for the very last expression, which doesn't belong there. – Barry Cipra Mar 23 '17 at 19:57
• What is the statement you're trying to prove? – Shaun Mar 24 '17 at 16:00
• @Shaun The author asked for a proof (by induction) that $$F_n=\frac{\left(\frac {1+\sqrt 5}2\right)^n-\left(\frac {1-\sqrt 5}2\right)^n}{\sqrt 5}$$ is equivalent to $$F_n=F_{n-1}+F_{n-2}$$ – user408202 Mar 24 '17 at 16:05
• @Shaun Thanks for your edit, I put the exact question #30 form the book to make it clear as to what I'm trying to prove. – user408202 Mar 24 '17 at 16:20