Inductive proof of a formula for Fibonacci numbers

Solution 1:

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$.

From your formula,

$$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$.

Solution 2:

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 \begin{equation} F_k=\frac{(\frac{1+\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k}}{\sqrt{5}} \end{equation} 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*}

Solution 3:

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).