How to find generating function of cumulative sum?

Given the recurrence, $$a_n = \begin{cases} 1, & n = 0 \\ a_{n-1} + 2a_{n-2} + 3a_{n-3} + \ldots + (n - 1)a_1 + na_0, & n \geq 1 \end{cases}$$ My attempt was, rewrite $a_n$ as: $$a_n = \displaystyle{\sum_{i=0}^na_i}(n - i) \Leftrightarrow \displaystyle{\sum_{n=0}^{\infty}a_nz^n} = \displaystyle{\sum_{n=0}^{\infty}\bigg(\displaystyle{\sum_{i=0}^na_i(n - i)\bigg)}}z^n + 1$$ then I tried to compare it with one of my generating function formulas: $$\dfrac{G(z)}{1 -z} = \displaystyle{\sum_{n=0}^{\infty}\bigg(\displaystyle{\sum_{i=0}^na_i\bigg)}}z^n$$ They're very similar except for the coefficient $n - i$ and the $1$. The answer given in the note was: $$a_n = \dfrac{-1}{\sqrt{5}}\bigg(\dfrac{2}{3 + \sqrt{5}}\bigg)^n + \dfrac{1}{\sqrt{5}}\bigg(\dfrac{2}{3 - \sqrt{5}}\bigg)^n$$ but I had no idea how did they get to that expression? I also tried to consider $$G(z) - zG(z) - 2z^2G(z) - 3z^3G(z) - 4z^4G(z) - \ldots = 1$$ but this approach leads to: $$G(z) = \dfrac{1}{1 - z - 2z^2 - 3z^3 - \ldots }$$ which is impossible to factor out the denominator. I guess there must be a clever trick to pull out the $n - i$ term but somehow I couldn't see it. I wonder could anyone give me a hint how to solve this problem? Thanks.

• For $n=0$, the answer given by the notes is $0$, but you it's defined as $1$. – Davide Giraudo Apr 12 '12 at 18:26
• Your second approach will work, it's just incomplete. There is a nice closed form for $z + 2z^2 + 3z^3 + ...$. – Qiaochu Yuan Apr 12 '12 at 18:27
• @Davide Giraudo: It's strange, probably typos from my teacher. Thanks for pointing that out. – Chan Apr 12 '12 at 18:31
• For my own exercise I've just made an attempt using a matrix-notation to show the most elementary operations which are required. Perhaps you like it; it can be found at go.helms-net.de/math/divers/mse/MSE120412.pdf – Gottfried Helms Apr 13 '12 at 12:45

As Qiaochu notes, your second approach works but is incomplete. Consider what the derivative of the usual geometric series looks like - can this be massaged into the form you have at hand?

More generally, if $(a)_n=a(a-1)\cdots\big(a-(n-1)\big)$, we can observe the following:

$$\frac{d^{\,k}}{dx^k} x^n = (n)_k x^{n-k} \quad\implies\quad \sum_{n=0}^\infty a_n (n)_k x^n =x^k\frac{d^{\,k}}{dx^k}\left(\sum_{n=0}^\infty a_nx^n\right).$$

Notice that $\{(n)_1,(n)_2,\cdots\}$ forms a basis for the vector space of integer coefficient polynomials, so we can use the above formula to evaluate, for any rational coefficient polynomial $P$,

$$A(x)=\sum_{n=0}^\infty a_n P(n) x^n \quad \mathrm{in~terms~of} \quad B(x)=\sum_{n=0}^\infty a_nx^n.$$

Going the other direction frequently involves differential equations. As an example, using the above ideas and your formula for $G(z)/(1-z)$ we can evaluate equation (2) in your question to

$$G(z)=z\frac{d}{dz}\left(\frac{G(z)}{1-z}\right)-\frac{1}{1-z}\left(z\frac{d}{dz} G(z)\right)+1.$$

See if you can prove $a_n=3a_{n-2}-a_{n-4}$. I assume that once you get it to that form, you have methods to solve it.