Fibonacci Recurrence Relations

Solve the recurrence relation $f(n) = f(n − 1) + f(n − 2)$ with initial conditions $f(0)=1$, $f(1)=2.$

So I understand that it grows exponentially so $f(n) = r^n$ for some fixed $r$. This means substituting this $r^n = r^n-1 + r^n-2$ which gives the characteristic equation of $r ^ 2 - r - 1 = 0$. I'm not 100% sure where to move on from here.

Now that you have $$r^2-r-1=0$$ solve for $r$ to get $$r=\frac{1\pm \sqrt{5}}{2}$$ now let $$r_+=\frac{1+ \sqrt{5}}{2}$$ and $$r_-=\frac{1- \sqrt{5}}{2}$$ And let us define the two sequences $a_n$ and $b_n$ as $$a_n=r_+^n$$ $$b_n=r_-^n$$ We can say that $$f(n)=c_1a_n+c_2b_n$$ Where $c_1$ and $c_2$ are some constants, since $a_n$ and $b_n$ both have the property that each term is the sum of the previous two. Now you need to find $c_1$ and $c_2$ so that $$c_1a_0+c_2b_0=2$$ $$c_1a_1+c_2b_1=1$$ Can you solve the system to find $c_1$ and $c_2$? Once you do that, you will have your formula: $$f(n)=c_1a_n+c_2b_n$$

Here is a formal derivation of your result. The sequence you have found is a generalization of the Fibonacci sequence.

There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas, and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$; available at http://ms.appliedprobability.org/data/files/Articles%2040/40-3-2.pdf.)

We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show that

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n) $$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.

The result is written in this form to underscore that it is the sum of a Fibonacci-type and Lucas-type Binet-like terms. It will also reduce to the standard Fibonacci and Lucas sequences for $a=b=1 \ \text{and} \ f_0=0,2 \text{ & } f_1=1$.

So, specializing to your case, we can say

$$ \alpha,\beta= \varphi,\psi(=-1/\varphi) $$

which are the usual Fibonacci values, since $a=b=1$. Then,

$$ \begin{align} f_n &=\left(2-\frac{1}{2}\right) \frac{\varphi^n-\psi^n}{\varphi-\psi}+\frac{1}{2} \left(\varphi^n+\psi^n\right)\\ &=\left(\frac{3}{2}\right) \frac{\varphi^n-\psi^n}{\varphi-\psi}+\frac{1}{2} \left(\varphi^n+\psi^n\right)\\ &=\frac{3}{2}F_n+\frac{1}{2}L_n \end{align} $$

where $F_n$ and $L_n$ are the Fibonacci and Lucas sequences, respectively. Of course, this analysis can be customized to any arbitrary initial condition problems.

EDIT NOTE (the following day)

There is a much simpler solution here. The initial conditions are in the Fibonacci sequence $(F_3 \text{ & } F_4)$ and the sequence is the Fibonacci sequence, therefore

$$f_n=F_{n+2}$$

This result is in agreement with my previous result. We can demonstrate that $\frac{3}{2}F_n+\frac{1}{2}L_n=F_{n+2}$ as follows:

$$ 3F_n+L_n=2F_{n+2}\\ L_n=F_n+2F_{n-1}\\ F_{n+2}=F_{n+1}+F_{n}=F_{n}+F_{n-1}+F_{n}=2F_n+F_{n-1}\\ 3F_n+F_n+2F_{n-1}=2(2F_n+F_{n-1}),\quad \text{QED} $$

Disclosure: this post is derived largely from a previous one: Decimal Fibonacci Number?