Binet Formula for Fibonacci Sequence

While there are many ways to derive the recursive formula of Fibonacci Sequence. The formula to find the nth term of a Fibonacci sequence is a beautiful formula. We are not going to derive here but prove the formula using mathematical Induction
We use Strong Induction to prove the Binet Formula because we will be invoking the recursive formula of fibonacci sequence to prove the $n+1$ case.
The Binet formula is $\frac{\phi^n-\alpha^n}{\sqrt{5}}$ $\phi = \frac{1+\sqrt{5}}{2}$ and $\alpha = \frac{1-\sqrt{5}}{2}$.
Verify the base cases: for $n = 1$ we have $\frac{\phi-\alpha}{\sqrt{5}}= 1$

Similarly for $n = 2$ we have $\frac{\phi^2-\alpha^2}{\sqrt{5}}$
$\Rightarrow \frac{(\phi-1)-(\alpha-1)}{\sqrt{5}}$
$\Rightarrow \frac{\phi-\alpha}{\sqrt{5}}$
which we know from first statement is true To prove the last step we realize that $F_{n+1}=F_n+F_{n-1}$
Thus we have $\Rightarrow F_{n+1}= \frac{\phi^n-\alpha^n}{\sqrt{5}}+\frac{\phi^{n-1}-\alpha^{n-1}}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^n+\phi^{n-1}-\alpha^n-\alpha^{n-1}}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n-1}(\phi+1)-\alpha^{n-1}(\alpha+1)}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n-1}(\phi^2)-\alpha^{n-1}(\alpha^2)}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n+1}-\alpha^{n+1}}{\sqrt{5}}$
Hence Proved