1
$\begingroup$

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.

$\endgroup$
4
  • 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 '19 at 23:49
  • $\begingroup$ @lulu could you show me how (in an answer)? $\endgroup$
    – clathratus
    May 25 '19 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 '19 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 '19 at 12:43
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh this is really neat! Thanks! $\endgroup$
    – clathratus
    May 26 '19 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.