Help me understand how to Find f(n) I have this question:


*

*$f(0) = 0$

*$f(1) = 1$

*$f(n) = f(n-1) + f(n-2)$
help me understand and find $f(n)$. 

Do you know Fibonacci rabbits?
That's a famous recurrence relation that we can solve by trial solution in the form $f(n)=x^n$ that is
$$x^{n}=x^{n-1}+x^{n-2}\implies x^2-x-1=0 \implies x_{1,2}=\frac{1\pm\sqrt 5}{2}$$
then
$$f(n)=c_1x_1^n+c_2x_2^n=c_1\left(\frac{1+\sqrt 5}{2}\right)^n+c_2\left(\frac{1-\sqrt 5}{2}\right)^n$$
and from the initial conditions $f(0)=0$ and $f(1)=1$ we obtain


*

*$c_1+c_2=0\implies c_1=-c_2=c$

*$c\left(\frac{1+\sqrt 5}{2}-\frac{1-\sqrt 5}{2}\right)=1\implies c=\frac1{\sqrt 5}$


and finally
$$f(n)=\frac1{\sqrt 5}\left(\frac{1+\sqrt 5}{2}\right)^n-\frac1{\sqrt 5}\left(\frac{1-\sqrt 5}{2}\right)^n$$
and indicating with $\phi=\frac{1+\sqrt 5}{2}$ the golden ratio we have that $\frac{1-\sqrt 5}{2}=-\frac1{\phi}$ and thus
$$f(n)=\frac1{\sqrt 5}\left(\phi\right)^n-\frac1{\sqrt 5}\left(-\frac1{\phi}\right)^n=\frac{\phi^{n}-(-\phi)^{-n}}{\sqrt 5}$$
