Help me understand how to Find f(n)

Question

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)$.

Answer 1

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}$$

Answer 2

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!