4
$\begingroup$

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.

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

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.

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$
    – Nirvana
    Oct 15 '14 at 16:24
  • $\begingroup$ Thanks for the edit $\endgroup$
    – Nirvana
    Oct 16 '14 at 1:55

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.