I am trying to solve this problem, where I am given a recurrence relation, for which I need to find all solutions.
The recurrence relation is as follows:
$a_n – 2na_{n-1} + n(n-1)a_{n-2} = 2nn!$, with initial conditions $a_0$ and $a_1$ = 1, and $n \geq 2$.
Using exponential generating functions, I have concluded that the generating function $A(x)$ of this recurrence relation, where $$A(x) = \sum_{n\geq 0} a_n \dfrac{x^n}{n!},$$ is given by $$A(x) = \dfrac{2x-3x(1-x)^2 + (1-x)^2}{(1-x)^4}$$.
How would I continue? I cannot see a way to transform this formula into something I can recognize? Normally when I reach this point I try to transform my function into something like one of these, from which I can then find my series.
Best Answer
Here's how I would expand your expression.
I'll use
$\begin{array}\\ (1-x)^{-s} &= \sum_{k=0}^{\infty} \binom{s+k-1}{k} x^k\\ &= \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} x^k\\ \text{so}\\ (1-x)^{-2} &= \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} x^k\\ &= \sum_{k=0}^{\infty} \binom{1+k}{1} x^k\\ &= \sum_{k=0}^{\infty} (k+1) x^k\\ \text{and}\\ (1-x)^{-4} &= \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} x^k\\ &= \sum_{k=0}^{\infty} \binom{3+k}{3} x^k\\ &= \sum_{k=0}^{\infty} \dfrac{(k+3)(k+2)(k+1)}{6} x^k\\ \end{array} $
$\begin{array}\\ A(x) &= \dfrac{2x-3x(1-x)^2 + (1-x)^2}{(1-x)^4}\\ &= \dfrac{2x}{(1-x)^4}-3\dfrac{x}{(1-x)^2}+\dfrac{1}{(1-x)^2}\\ &= (2x)\sum_{k=0}^{\infty} \dfrac{(k+3)(k+2)(k+1)}{6} x^k-3x\sum_{k=0}^{\infty} (k+1) x^k+\sum_{k=0}^{\infty} (k+1) x^k\\ &= \sum_{k=0}^{\infty} \dfrac{2(k+3)(k+2)(k+1)}{6} x^{k+1}-3\sum_{k=0}^{\infty} (k+1) x^{k+1}+\sum_{k=0}^{\infty} (k+1) x^k\\ &= \sum_{k=1}^{\infty} \dfrac{(k+2)(k+1)k}{3} x^{k}-3\sum_{k=1}^{\infty} kx^k+\sum_{k=0}^{\infty} (k+1) x^k\\ &= \sum_{k=1}^{\infty}\left( \dfrac{(k+2)(k+1)k}{3} -3k+(k+1)\right) x^k+1\\ &=1+ \sum_{k=1}^{\infty}\left( \dfrac{3(-2k+1)+k^3+3k^2+2k}{3}\right) x^k\\ &=1+ \sum_{k=1}^{\infty}\left( \dfrac{k^3+3k^2-4k+3}{3}\right) x^k\\ \end{array} $