# Exponential Generating function for inhomogenous recurrence relation

I want to determine all solutions to the recurrence relation

$$a_n−2na_{n−1}+n(n−1)a_{n−2} = 2n·n!, \ \ \ n≥2, a_0 = a_1 = 1.$$

by using exponential generating functions.

My idea was something like that: $$\sum_{n\geq2} a_n \frac{z^n}{n!}−\sum_{n\geq2}2na_{n−1} \frac{z^n}{n!}+\sum_{n\geq2}n(n−1)a_{n−2} \frac{z^n}{n!} - \sum_{n\geq2}2n\frac{z^n}{n!} = 0 \\$$

Denoting

$$Â(z) =\sum_{n\geq0} a_n \frac{z^n}{n!}$$

which is the exponential generating function, I can derive that $$\sum_{n\geq2}2na_{n−1} \frac{z^n}{n!}$$ is $$z^2 Â'(z)$$ and for $$\sum_{n\geq2}2n\frac{z^n}{n!}$$, that $$zÂ(2z)$$ (which I am also not 100% sure of). However, I get stuck for the third summation term. How would I continue, am I even on the right path?

• You're definitely on the right path! Don't forget the $2$ on the 2nd term. The last term should be $\sum {2n\cdot n!\cdot\frac{z^n}{n!}}$, which will be related to a geometric series (it has nothing to do with $A(z)$). As for the 3rd term, see if you can interpret it in terms of $A''(z)$. Nov 24, 2020 at 17:20
• Seems like you're on the right path, but check the term $z^2A'(z)$ it should equal $\Sigma na_{n}\frac{z^{(n+1)}}{n!}$ which isn't exactly what you want, I got $2(zA(z)-z)$ for the first term, you can check it for yourself.
– Mars
Nov 24, 2020 at 17:34
• @Mars If you multiply by $z^n$ and divide by $n!$ then last term should be $2nz^n$ whose sum is $$\sum _{n=2}^{\infty } 2 n z^n=\frac{2 (z-2) z^2}{(z-1)^2}$$ Nov 24, 2020 at 19:21
• @Raffaele Ah, I see now. Thank you for catching that mistake, I updated my answer.
– Mars
Nov 24, 2020 at 21:48

For the first term $$\sum_{n\geq2} a_n \frac{z^n}{n!}$$ I get $$Â(z)-1-z$$ by taking care of the first two initial conditions. For the second term $$\sum_{n\geq2}2na_{n−1} \frac{z^n}{n!}$$ I get $$2(zÂ(z)-z)$$, notice $$\frac{n}{n!}=\frac{1}{(n-1)!}$$ and that taking derivatives shift the index of $$a_n$$ up, multiplying by z shifts the index of $$a_n$$ down. The -z is obtained by accounting for initial conditions.
For the third term $$\sum_{n\geq2}n(n−1)a_{n−2} \frac{z^n}{n!}$$ I get $$z^2Â(z)$$. Notice that $$\frac{n(n-1)}{n!}=\frac{1}{(n-2)!}$$.
For the fourth term is actually $$\sum_{n\geq 2}2nz^n$$ I get $$\frac{2(z-2)z^2}{(z-1)^2}$$. Because $$\sum_{n\geq 1}nz^n=\frac{z}{(1-z)^2}$$ and taking out the first term we get $$\sum_{n\geq 2}nz^n=\frac{z}{(1-z)^2}-z=\frac{z(1-(1-z)^2)}{(1-z)^2}=\frac{z^2(2-z)}{(1-z)^2}$$.