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 \\ $$


$$Â(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?

  • $\begingroup$ 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)$. $\endgroup$ Nov 24, 2020 at 17:20
  • $\begingroup$ 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. $\endgroup$
    – Mars
    Nov 24, 2020 at 17:34
  • $\begingroup$ @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}$$ $\endgroup$
    – Raffaele
    Nov 24, 2020 at 19:21
  • $\begingroup$ @Raffaele Ah, I see now. Thank you for catching that mistake, I updated my answer. $\endgroup$
    – Mars
    Nov 24, 2020 at 21:48

1 Answer 1


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}$.

  • $\begingroup$ Can you maybe explain how you came up with the solution for the 4th term? $\endgroup$ Nov 24, 2020 at 18:43
  • $\begingroup$ @NikollosXerxes Yeah I'll edit my post now. $\endgroup$
    – Mars
    Nov 24, 2020 at 18:59

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.