<s>[INST] 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}$$
 [/INST] 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. 
</s>