Recurrence $f_{n+2}=af_{n+1}+bf_n$

Question

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.

Answer 1

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.