## Fibonnaci sequence

Prove by mathematical induction that for the Fibonacci sequence $$F_1=F_2=1$$, $$F_n=F_{n-1}+F_{n-2}$$ the following holds: $$\displaystyle \sqrt{5}F_n= \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n$$.
For $$n=1$$ we have $$\sqrt{5}=\frac{1+\sqrt5}2-\frac{1-\sqrt5}2$$.
For $$n=2$$ we have $$\sqrt{5}=\frac{3+\sqrt5}2-\frac{3-\sqrt5}2=\left(\frac{1+\sqrt{5}}{2}\right)^2-\left(\frac{1-\sqrt{5}}{2}\right)^2$$.
We prove the statement for $$n+1$$ given that it holds for $$n$$ and $$n-1$$:
$$\displaystyle \sqrt{5}F_{n+1}=\sqrt{5}F_n+\sqrt{5}F_{n-1}= \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n+ \left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}=$$
$$= \left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1+\sqrt{5}}{2}\right)^{n-1} -\left[\left(\frac{1-\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right]= \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}$$