Solve the recurrence relation
$$f(n) = f(n - 1) + f(n - 2)$$
with initial conditions $f(0) = 2, f(1) = 1$. Give full details.
The following is what I have done:
- try $f(n) = r^n$, for some fixed $r$.
- $r^n = r^{n - 1} + r^{n - 2}$
- equation = $r^2 - r - 1 = 0$, if $n = 2$
HINT:
$$r^2 - r - 1 = 0 \to r_1,r_2\\r_1=\frac{1+\sqrt5}{2}\\r_2=\frac{1-\sqrt5}{2}$$so $f(n)$ must be $$f(n)=a.r_1^n+b.r_2^n$$then apply initial conditions
can you go on ?
$$f(n)=a(\frac{1+\sqrt5}{2})^n+b(\frac{1-\sqrt5}{2})^n$$put $f(0)=2\to f(0)=a.1+b.1=2$
now put $n=1 \to f(1)=1 \to a(\frac{1+\sqrt5}{2})^1+b(\frac{1-\sqrt5}{2})^1=1$
then solve the system of equation to find a,b
\begin{cases}a+b & = 2\\a(\frac{1+\sqrt5}{2})+b(\frac{1-\sqrt5}{2}) & =1\end{cases}
\begin{cases}(\sqrt5-1)a+(\sqrt5-1)b & = 2(\sqrt5-1)\\a(1+\sqrt5)+b(1-\sqrt5) & =2\end{cases}
$$\to 2a\sqrt5=2\sqrt5 \to a=1\\b=1$$
so
$$f(n)=a(\frac{1+\sqrt5}{2})^n+b(\frac{1-\sqrt5}{2})^n\\=(\frac{1+\sqrt5}{2})^n+(\frac{1-\sqrt5}{2})^n$$
check for n=1,0
$$f(0)=(\frac{1+\sqrt5}{2})^n+(\frac{1-\sqrt5}{2})^0=1+1=2\\f(1)=(\frac{1+\sqrt5}{2})+(\frac{1-\sqrt5}{2})=1$$
