# Solving recurrence -varying coefficient

How can one find a closed form for the following recurrence? $$r_n=a\cdot r_{n-1}+b\cdot (n-1)\cdot r_{n-2}\tag 1$$

(where $a,b,A_0,A_1$ are constants and $r_0=A_0,r_1=A_1$)

If the $(n-1)$ was not present, this could easily be solved using a characteristic equation. However, with the varying coefficient, the process is not so simple.

• By solving you mean finding a closed-form expression for $r_n$? Otherwise there is not much to solve right here. Oct 15 '14 at 15:30
• Yes closed form Oct 15 '14 at 15:47

The e.g.f.'s $\sum_{n=0}^\infty r_n t^n/n!$ for two linearly independent solutions are $\exp(b t^2/2 + a t)$ and $\exp(b t^2/2 + a t)\; \text{erf}(\sqrt{b/2} t + a/\sqrt{2b})$.
From the first, we get $$r_n = n! \sum_{k=0}^{\lfloor n/2 \rfloor} \dfrac{ (b/2)^k a^{n-2k}}{k! (n-2k)!}$$
EDIT: Here's a little explanation. The e.g.f. (exponential generating function) of a sequence $r_n$ is the function $g(t) = \sum_{n=0}^\infty r_n t^n/n!$. This has the nice property that $g'(t) = \sum_{n=0}^\infty r_{n+1} t^n/n!$, $g''(t) = \sum_{n=0}^\infty r_{n+2} t^n/n!$, etc., while $$\sum_{n=0}^\infty n\; r_n \dfrac{t^n}{n!} = \sum_{m=0}^\infty r_{m+1}\dfrac{ t^{m+1}}{m!} = t g'(t)$$ Now write your recurrence as $$r_{n+2} = a \; r_{n+1} + b\; (n+1) r_{n} = a \; r_{n+1} + b \; r_n + b\; n r_n$$ Multiply each term by $t^n/n!$ and sum. We get $$g''(t) = a g'(t) + b g(t) + b t g'(t)$$ and two linearly independent solutions to this differential equation are $$g(t) = \exp(b t^2/2 + a t) \ \text{and} \ g(t) = \exp(b t^2/2 + a t)\; \text{erf}\left(\sqrt{b/2}\; t + a/\sqrt{2b}\right)$$ If $a$ and $b$ are matrices that don't commute, things are not so simple: it's no longer true that $\dfrac{d}{dt} \exp(b t^2/2 + a t) = ( bt + a) \exp(b t^2/2 + a t)$. Even for the $2 \times 2$ case I don't think you'll get closed-form solutions.
• Would you add bit explanation thanks and will it work for matrices means if $r$ is $3 \times 1$ and $a,b$ is $3 \times 3$ Oct 15 '14 at 16:24