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.

  • 1
    $\begingroup$ The usual method is to study the characteristic polynomial. As this is quadratic in your case, you can work it all out quite explicitly. $\endgroup$
    – lulu
    May 25, 2019 at 23:49
  • $\begingroup$ @lulu could you show me how (in an answer)? $\endgroup$
    – clathratus
    May 25, 2019 at 23:52
  • $\begingroup$ I attached a link which works it all out. That link uses the Fibonacci recursion as a concrete example. $\endgroup$
    – lulu
    May 25, 2019 at 23:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – user21820
    Jun 9, 2019 at 12:43

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .