Recursive/Fibonacci Induction 1) Let $F_n$ denote the $n^t$$^h$ Fibonacci number. Prove by induction:  

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

Clear explanation would be appreciated.
 A: There's a clear explanation on this link Fibonacci series . Key point of the $n$th term of a fibonacci series is the use of golden ratio.  $\phi  =\dfrac{1+\sqrt5}{2}$. There has been a use of Matrices in the proof.
A: Put $$\varphi=\frac{1+\sqrt 5}2,\;\lambda=\frac{1-\sqrt5}2.$$ These are the roots to the quadratic equation $x^2-x-1=0,$ so in particular, we have $$\varphi^2=\varphi+1,\;\lambda^2=\lambda+1.$$ Note also that $$\varphi-\lambda=\sqrt5,\;\lambda+\varphi=1.$$
Since $F_0=F_1=1,$ then $\varphi-\lambda=\sqrt5$ gives us the first base case, so that $$F_1=F_0=\frac1{\sqrt5}(\varphi-\lambda)=\frac1{\sqrt5}\bigl((\varphi+1)-(\lambda+1)\bigr)=\frac1{\sqrt5}(\varphi^2-\lambda^2)$$ gives us the second base case.
Now suppose $F_n=\frac1{\sqrt5}(\varphi^{n+1}-\lambda^{n+1})$ and $F_{n+1}=\frac1{\sqrt5}(\varphi^{n+2}-\lambda^{n+2})$ for some $n.$ Note that $$\varphi^{n+1}-\lambda^{n+1}=(\varphi-\lambda)\sum_{k=0}^n\varphi^{n-k}\lambda^k=\sqrt5\sum_{k=0}^n\varphi^{n-k}\lambda^k$$ and likewise $$\varphi^{n+2}-\lambda^{n+2}=\sqrt5\sum_{k=0}^{n+1}\varphi^{n+1-k}\lambda^k,$$ so $$\begin{align}F_{n+2} &= F_n+F_{n+1}\\ &= \sum_{k=0}^n\varphi^{n-k}\lambda^k+\sum_{k=0}^{n+1}\varphi^{n+1-k}\lambda^k\\ &= \lambda^{n+1}+\sum_{k=0}^n\varphi^{n-k}\lambda^k+\sum_{k=0}^n\varphi^{n+1-k}\lambda^k\\ &= \lambda^{n+1}+\sum_{k=0}^n\varphi^{n-k}\lambda^k+\varphi\sum_{k=0}^n\varphi^{n-k}\lambda^k\\ &= 1\cdot\lambda^{n+1}+(1+\varphi)\sum_{k=0}^n\varphi^{n-k}\lambda^k.\end{align}$$ Now, recalling that $\varphi+\lambda=1$ and $1+\varphi=\varphi^2,$ we have $$\begin{align}F_{n+2} &= (\varphi+\lambda)\cdot\lambda^{n+1}+\varphi)^2\sum_{k=0}^n\varphi^{n-k}\lambda^k\\ &= \varphi\lambda^{n+1}+\lambda^{n+2}+\sum_{k=0}^n\varphi^{n+2-k}\lambda^k\\ &= \sum_{k=0}^{n+2}\varphi^{n+2-k}\lambda^k\\ &= \frac1{\varphi-\lambda}(\varphi-\lambda)\sum_{k=0}^n\varphi^{n+2-k}\lambda^k\\ &= \frac1{\varphi-\lambda}(\varphi^{n+3}-\lambda^{n+3}),\end{align}$$ and since $\varphi-\lambda=\sqrt5,$ the induction step is completed.
A: Hint (if you know something about discrete dynamical systems)
you can look for solutions of the d.d.s. of the form $A \lambda_1^n + B\lambda_2^n$, where $\lambda_i$ are the solutions of the associated equation $p(\lambda) = \lambda^2 - \lambda - 1 = 0$. $A,B$ are to be determined by the initial condition $F_0 = 0$, $F_1 = 1$.
