Solve the recurrence $$f_{n+2}=af_{n+1}+bf_n\qquad n\in\Bbb N_0\tag{1}$$
Where $a,b>0$ and $f_0,f_1$ are given.
I know that if $$F_{n+1}=c_nF_n+d_n$$ then $$F_n=F_0\prod_{k=0}^{n-1}c_k+\sum_{m=0}^{n-1}d_m\prod_{k=m+1}^{n-1}c_k\ .$$
But I am unsure of how to find a solution to the recurrence in question. I am fairly certain that a closed form exists, because the Fibonacci sequence $F_n$ (which is given by the case $a=b=f_1=1$ and $f_0=0$) has an explicit solution, namely
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5}$$ where
$$\varphi=\frac{1+\sqrt5}2,\qquad \psi=\frac{1-\sqrt5}2\,.$$
Admittedly, I do not know how to prove said result, but I'm sure there is some sort of generalization of the proof to solve my recurrence.
I've defined the generating function
$$f(x)=\sum_{n\geq0}f_nx^n$$
and shown that
$$f(x)=\frac{f_0+(f_1-af_0)x}{1-ax-bx^2}\ .$$
So of course $$f_n=\frac1{n!}\left(\frac{\partial}{\partial x}\right)^n\frac{f_0+(f_1-af_0)x}{1-ax-bx^2}\,\Bigg|_{x=0}$$
but that is way too inefficient. Is there a nice closed form solution for $(1)$? Thanks.
Best Answer
You start by finding two geometric sequences that solve
$$x^{n+2} = ax^{n+1}+bx^n\tag{A.}$$
Solving for $x$, we get
\begin{align} x^{n+2} &= ax^{n+1}+bx^n \\ x^2 &= ax+b \\ x^2 - ax -b &= 0 \\ x &= \frac{a\pm\sqrt{a^2+4b}}{2} \end{align}
From here on, we have to assume that $a^2+4b \ne 0$.
Then $f_n = \alpha\left(\dfrac{a + \sqrt{a^2+4b}}{2}\right)^n + \beta\left(\dfrac{a - \sqrt{a^2+4b}}{2}\right)^n$
will solve $f_{n+2}=af_{n+1}+bf_n$ for all $n \ge 0$.
We still need to solve $f_0 = \alpha + \beta$ and $f_1=\alpha\left(\dfrac{a + \sqrt{a^2+4b}}{2}\right) + \beta\left(\dfrac{a - \sqrt{a^2+4b}}{2}\right)$ for $\alpha$ and $\beta$, but that is relatively trivial.