Prove by induction (Fibonacci) $F_n=\frac{\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt5}$ Can someone advise on proving the following by induction. I'm assuming strong induction should be used here?
Here $F_n$ is the $n$th Fibonacci number. Prove that
$$F_n=\frac{\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt5}$$
 A: Yes, go with induction.
First, check the base case $$F_1=1$$ That should be easy.
For the inductive step, consider, on the one hand: 
(1) $$F_{n+1}= F_n+F_{n-1}$$ 
Then, write what you need to prove, to have it as a guidance of what you need to get to. That is: 
$$F_{n+1}=\frac{\left(\frac{1+\sqrt 5}{2}\right)^{n+1}-\left(\frac{1-\sqrt 5}{2}\right)^{n+1}}{\sqrt5}$$ 
Use (1) and your hypothesis and write 
$$F_{n+1}= \frac{\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt5} + $$ $$\frac{\left(\frac{1+\sqrt 5}{2}\right)^{n-1}-\left(\frac{1-\sqrt 5}{2}\right)^{n-1}}{\sqrt5}$$ 
this translates to
$$= {\frac {1} {\sqrt5}}[{\left(\frac{1+\sqrt 5}{2}\right)^{n}\left(1+\frac{2}{1+\sqrt 5}\right)}-{\left(\frac{1-\sqrt 5}{2}\right)^{n}\left(1+\frac{2}{1-\sqrt 5}\right)}]$$

To finish, note that (a) $${\left(1+\frac{2}{1+\sqrt 5}\right)}{\left(\frac{1-\sqrt 5}{1-\sqrt 5}\right)}={\frac {1+\sqrt 5}{2}}$$
and (b)
$${\left(1+\frac{2}{1-\sqrt 5}\right)}{\left(\frac{1+\sqrt 5}{1+\sqrt 5}\right)}={\frac {1-\sqrt 5}{2}}$$
which is exactly what you need to end the proof. 
A: $$F_n=\frac{\phi^n-\psi^n}{\sqrt5}$$
Then the recurrence relation can be written
$$F_{n+2}-F_{n+1}-F_n=\frac{\phi^2\phi^n-\psi^2\psi^n}{\sqrt5}-\frac{\phi\phi^n-\psi\psi^n}{\sqrt5}-\frac{\phi^n-\psi^n}{\sqrt5}=0.$$
The identify holds if
$$\phi^2-\phi-1=\psi^2-\psi-1=0,$$ which is precisely the case.
The base cases for $F_0=0$ and $F_1=1$ are easy to check.
A: It's enough for your induction to work to know that the previous two satisfy this equality. So the induction would work like this:
1) Base. Check that $ F_0, F_1 $ satisfy the equality
2) Step. Assume that $ F_{n-2}, F_{n-1} $ satisfy the equality and derive $ F_n $ for $ n > 1 $
More details can be found here 
