# 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 '19 at 23:49
• @lulu could you show me how (in an answer)? May 25 '19 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 '19 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 '19 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.

• Oh this is really neat! Thanks! May 26 '19 at 2:08