# Expression for recurrence relation $a_n$ using exponential generating functions

$a_0 = 2$, $a_n = na_{n - 1} - n!$ for $n \geq 1$.

Let $$f(x) = \sum_{n \geq 0}a_n\frac{x^n}{n!}.$$

Multiplying each term in the relation by $\frac{x^n}{n!}$ and summing over values for which the relation is defined and we get:

\begin{align*} \sum_{n \geq 1} a_n\frac{x^n}{n!} &= \sum_{n \geq 1}na_{n - 1}\frac{x^n}{n!} - \sum_{n \geq 1}n!\frac{x^n}{n!}\\ f(x) - a_0 &= x\sum_{n \geq 1}a_{n - 1}\frac{x^{n - 1}}{(n - 1)!} - \sum_{n \geq 1}n!\frac{x^n}{n!}\\ f(x) - 2 &= x \cdot f(x) - \left(\frac{1}{1 - x} - 0!\right)\\ f(x) - 2 &= x \cdot f(x) - \frac{x}{1 - x}\\ f(x) - x \cdot f(x) &= 2 - \frac{x}{1 - x}\\ f(x)\left[1 - x\right] &= \frac{2 - 3x}{1 - x}\\ f(x) &= \frac{2 - 3x}{(1 - x)^2} \end{align*}

After this, we're supposed to find the coefficient of $\frac{x^n}{n!}$ to find a concise expression for $a_n$. However, I've hit several dead ends. Basically I don't know how to play with

$$f(x) = \frac{2 - 3x}{(1 - x)^2}$$

to find the coefficient. Do I use convolution? Partial fraction decomposition? I have no clue.

• This is the simplest when you leave the function as $\frac{2}{1-x} - \frac{x}{(1-x)^2}$. The first is the series $2\sum_0^\infty x^k$ and the second is $\sum_0^\infty k x^{k+1}$. – stochasticboy321 Nov 6 '15 at 2:05
• To check these (furious) computations, note that $a_0=2$ and $\frac{a_n}{n!}=\frac{a_{n-1}}{(n-1)!}-1$ hence $\frac{a_n}{n!}=2-n$ for every $n\geqslant0$, that is, $a_n=(2-n)\cdot n!$. – Did Nov 6 '15 at 7:44

\begin{align} n! [x^n] \frac{2 - 3 x}{(1 - x)^2} &= n! [x^n] (2 - 3 x) (1 - x)^{-2} \\ &= n! \left( 2 [x^n] (1- x)^{-2} - 3 [x^{n - 1}] (1 - x)^{-2} \right) \\ &= n! \left( 2 (-1)^n \binom{-2}{n} - 3 (-1)^{n - 1} \binom{-2}{n - 1} \right) \\ &= n! \left( 2 \binom{n + 2 - 1}{2 - 1} - 3 \binom{n - 1 + 2 - 1}{2 - 1} \right) \\ &= n! \left( 2 \binom{n + 1}{1} - 3 \binom{n}{1} \right) \\ &= n! \left( 2 (n + 1) - 3 n \right) \\ &= - n! (n - 2) \end{align}