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.
 A: 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$.
A: 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*}
A: 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).
