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.
 A: 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.$$
A: 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. 
