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)$. 
 A: 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}$$
A: Adding to @gimusi 's answer, if you divide $f(n+1)$ by $f(n)$, then this approaches a certain value, for all $n\in\mathbb{N}$. We will call this value $v$, then $$\frac{f(n+1)}{f(n)}\operatorname*{\longrightarrow}^{n\to\infty} v,$$ or $$\lim_{n\to\infty}\frac{f(n+1)}{f(n)} = v.$$ Whichever choice of notation you prefer. After going here, we find that $$v^2 - v - 1 = 0.\tag{In the link, $v = \Delta$}$$ Do you know the quadratic formula? If so, you can apply it to this equation and obtain that $$v = \frac{1+\sqrt{5}}{2} = \color{orange}{\verb|The Golden Ratio|}\tag{denoted by $\varphi$}.$$
This is why the sequence you have, known as the Fibonacci Sequence, is very well-known!
