The problem is this:
Prove by using induction that the Fibonacci equation has the solution
$\ F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$
Yeah I know for example you start with the very first n = 1 and then you try for any given n =p and the last part where n = p +1 I dont get how to do the last part
On
Hint:
Let $\phi=\dfrac{1+\sqrt5}2$ and $\psi=\dfrac{1-\sqrt5}2$.
Can you show $\phi^2=\phi+1$ and $\psi^2=\psi+1$,
so $\phi^{n+1}=\phi^{n}+\phi^{n-1}$ and $\psi^{n+1}=\psi^n+\psi^{n-1}$,
so $\dfrac{\phi^{n+1}-\psi^{n+1}}{\sqrt5}=\dfrac{\phi^{n}-\psi^{n}}{\sqrt5}+\dfrac{\phi^{n-1}-\psi^{n-1}}{\sqrt5}$?
The sketch would be...
Show that $f_1 = 1$ and $f_2 = 1$
This covers your base cases.
Take note that $\left(\frac {1+\sqrt 5}{2}\right)^2= 1+\frac {1+\sqrt 5}{2}$ and $\left(\frac {1-\sqrt 5}{2}\right)^2= 1+\frac {1-\sqrt 5}{2}$
This will be useful in proving the inductive step.
Suppose for all $k\le n, f_k = F_k.$ This is "strong induction."
$F_{k+1} = F_k + F_{k-1}$ by the definition of the Fibonacci sequence
If we can show that $f_n+f_{n-1} = f_{n+1}$ then we are done. We will that when it is true for all $k\le n$ we can extend that to all $k\le n+1$ and keep extending that indefinitely.
The rest is just algebra.