Generating Function for a Recurrence Relation $a_n=a_{n-1} + n$

Question

Find a generating function for $\{a_n\}$ where $a_0=1$ and $a_n=a_{n-1} + n$

Answer 1

Multiply both sides of the recurrence by $x^n$ and sum over all $n\ge 1$ to get

\begin{align}\sum_{n \ge 1} a_n x^n &= \sum_{n \ge 1} a_{n-1}x^n + \sum_{n\ge 1} nx^n\\ \sum_{n\ge 1} a_nx^n &= x\sum_{n\ge 1} a_{n-1}x^{n-1} + x\sum_{n\ge 1} nx^{n-1}\\ \sum_{n\ge 1} a_n x^n &= x\sum_{n\ge 0} a_n x^n + x\frac{d}{dx}\sum_{n\ge 1} x^n\\ \sum_{n\ge 0} a_n x^n - 1&= x \sum_{n\ge 0} a_n x^n + x\frac{d}{dx}\frac{x}{1 - x}\\ (1 - x)\sum_{n\ge 0} a_n x^n &= 1 + \frac{x}{(1 - x)^2}\\ \sum_{n\ge 0} a_n x^n &= \frac{1}{1 - x} + \frac{x}{(1 - x)^3}. \end{align}

Answer 2

Hint $a_{n}-a_0=\sum_{i=1}^{n}(a_i-a_{i-1})$

Answer 3

By definition of the generating function,

$$G(z)=\sum_{n=0}^\infty a_nz^n=a_0+\sum_{n=1}^\infty a_nz^n.$$ Applying the recurrence relation, $$G(z)=a_0+\sum_{n=1}^\infty (a_{n-1}+n)z^n =a_0+z\sum_{n=1}^{\infty}a_{n-1}z^{n-1}+\sum_{n=1}^\infty nz^n=a_0+zG(z)+\frac z{(1-z)^2}.$$

Solve for $G(z)$.