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

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.

• The usual method is to study the characteristic polynomial. As this is quadratic in your case, you can work it all out quite explicitly.
– lulu
May 25, 2019 at 23:49
• @lulu could you show me how (in an answer)? May 25, 2019 at 23:52
• I attached a link which works it all out. That link uses the Fibonacci recursion as a concrete example.
– lulu
May 25, 2019 at 23:52
• Related, the most efficient way to compute the $n$-th Fibonacci number (or in general the $n$-th term of any non-trivial recurrence relation) is to use the matrix form and iterated squaring, rather than the closed form, because exponentiation of irrationals to arbitrary precision is actually very computationally expensive. Jun 9, 2019 at 12:43

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.