Inductive proof of a formula for Fibonacci numbers

May someone help me? I am trying to use induction to prove that the formula for finding the $n$-th term of the Fibonacci sequence is:

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

I tried to put $n=1$ into the equation and prove that if $n=1$ works then $n=2$ works and it should work for any number, but it didn't work. I need to prove that this formula gives the $n$th Fibonacci number.

• Have you done anything yourself yet? – 5xum Aug 4 '14 at 10:00
• – Shaun Aug 4 '14 at 10:01
• This is not the best written proof I've seen, but it should be good enough for you. csee.wvu.edu/~ksmani/courses/fa04/at/qen/fib.pdf – Darth Geek Aug 4 '14 at 10:05
• You are a new user, so you may be surprised why your question was downvoted and flagged for closing. It is because you showed no effort to answer your question alone, and also you have been completely unresponsive to any answers since you asked the question. – 5xum Aug 4 '14 at 10:12
• "$\sqrt(1+5\sqrt{2})n$" seems very strange. – JiK Aug 12 '14 at 8:25

Let $\phi=\dfrac{\sqrt{5}+1}2$ and note that $\phi^{-1} =\dfrac 1\phi= \dfrac{\sqrt{5}-1}2$.

Note also that $1+\dfrac 1\phi=\phi$ and $1-\phi=-\dfrac 1\phi$.

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

For $n=k$ and $n=k-1$, \begin{align} F_k &= \frac 1{\sqrt{5}}\left[\phi^k-(-\frac 1\phi)^k \right]\\ F_{k-1} &= \frac 1{\sqrt{5}}\left[\phi^{k-1}-(-\frac 1\phi)^{k-1} \right]\\ &=\frac 1{\sqrt{5}} \left[\phi^k \cdot \frac 1\phi -(-\frac 1\phi)^k \cdot (-\phi)\right]\\ \end{align} Hence,

\begin{align} F_{k+1}&=F_{k}+F_{k-1}\\ &=\frac 1{\sqrt{5}} \left[\phi^k \cdot \left( 1+\frac 1\phi \right) -(-\frac 1\phi)^k \cdot \left( 1-\phi \right)\right]\\ &=\frac 1{\sqrt{5}} \left[\phi^k \cdot \phi -(-\frac 1\phi)^k \cdot \left( -\frac 1\phi \right)\right]\\ &=\frac 1{\sqrt{5}} \left[\phi^{k+1}-(-\frac 1\phi)^{k+1} \right] \end{align}

i.e. if formula is true for $n=k-1$ and $n=k$, it is also true for $n=k+1$.

For $n=0$ and $n=1$, $F_0=0$ and $F_1=1$ respectively. Hence $F_2=F_0+F_1=1$. It can easily be shown that the formula is true for $n=2$.

Hence, by induction, formula is true for all positive integer $n\geq 2$.

• You're welcome :) – hypergeometric Aug 12 '14 at 14:36

Proof: Let n=1 thus, \begin{align*} F_1&=\frac{(\frac{1+\sqrt{5}}{2})^{1}-(\frac{1-\sqrt{5}}{2})^{1}}{\sqrt{5}}\\ &=\frac{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}{\sqrt{5}}\\ &=\frac{\frac{1+\sqrt{5}-1+\sqrt{5}}{2}}{\sqrt{5}}\\ &=\frac{\frac{\sqrt{5}+\sqrt{5}}{2}}{\sqrt{5}}\\ &=\frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}}\\ &=\frac{{\sqrt{5}}}{\sqrt{5}}\\ &=1 \end{align*} Suppose $$F_k=\frac{(\frac{1+\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k}}{\sqrt{5}}$$ Also $F(k+1)=F(k)+F(k-1)$ \begin{align*} F(k)+F(k-1)&=\frac{(\frac{1+\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k}}{\sqrt{5}}+\frac{(\frac{1+\sqrt{5}}{2})^{k-1}-(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{(\frac{1+\sqrt{5}}{2})^{k}+(\frac{1+\sqrt{5}}{2})^{k-1}-(\frac{1-\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{((\frac{1+\sqrt{5}}{2})+1)(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{1-\sqrt{5}}{2})+1)(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{((\frac{3+\sqrt{5}}{2}))(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{3-\sqrt{5}}{2}))(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{((\frac{1+\sqrt{5}}{2})^{2})(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{1-\sqrt{5}}{2})^{2})(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{(\frac{1+\sqrt{5}}{2})^{k+1}-(\frac{1-\sqrt{5}}{2})^{k+1}}{\sqrt{5}}\hfill \end{align*}

• This is a good proof but you should have two bases cases $F_1$ and $F_0$ for the inductive step to work. I.e. at the moment you can not prove $F_2$ is true as it relies upon $F_1$ and $F_0$ being true. – Ian Miller Oct 28 '16 at 15:32
• @IanMiller Is that way the inductive hypothesis has an "also", because it is two inductive hypotheses? – GFauxPas Oct 28 '16 at 16:26

By denoting with $$\sigma = \frac{1+\sqrt{5}}{2},\qquad \bar{\sigma}=\frac{1-\sqrt{5}}{2}$$ we have that $\sigma,\bar{\sigma}$ are the roots of the polynomial $x^2-x-1$. This gives: $$\sigma^2 = \sigma+1,\qquad \sigma^{n+2}=\sigma^{n+1}+\sigma^n,$$ $$\bar{\sigma}^2 = \bar{\sigma}+1,\qquad \bar{\sigma}^{n+2}=\bar{\sigma}^{n+1}+\bar{\sigma}^n,$$ hence any sequence $\{a_n\}_{n\in\mathbb{N}}$ defined by: $$a_n = k_0 \,\sigma^n + k_1\, \bar{\sigma}^n$$ satisfies the recurrence relation: $$a_{n+2} = a_{n+1} + a_n.$$ You just have to check that with the choices $k_0=\frac{1}{\sqrt{5}},k_1=-\frac{1}{\sqrt{5}}$ we have: $$a_0=F_0=0,\qquad a_1=F_1=1,$$ since this condition implies $a_n=F_n$ by induction.

The spirit is the same of the Cauchy-Lipshitz theorem: the same differential equation (the same recurrence relation) and the same boundary conditions (the same starting values) give the same function (sequence).

• This does not answer the original question. It does not show to the OP how to use induction (which seems to be his question). – 5xum Aug 4 '14 at 10:11
• @5xum: On my planet, proving that $$a_n=F_n,a_{n+1}=F_{n+1}\quad\Longrightarrow\quad a_{n+2}=F_{n+2}$$ (provided that $a_{n+2}=a_{n+1}+a_n$) is using induction in the most natural way. – Jack D'Aurizio Aug 4 '14 at 10:14
• Regardless of whether this is induction, learning shouldn't stop once the exercise has been completed within the homework's arbitrary rules. It's good to be exposed to many different solutions. – Kaj Hansen Aug 4 '14 at 10:15