find the generating function for $a_n = n^3$

Question

For my upcoming exam I'm dealing with the topic generating function. I found an exercise, that I want to solve.

first one: $a_n = a_{n-1} +1 $ , $a_0 = 1 $.

second one: $ a_n = n^3$. ( my actual question )

first one: this was easy. Here is my solution:

$A(x) = \sum_{n \geq 0} a_nx^n = a_0 + \sum_{n \geq 1} (a_{n-1}+1)x^n = 1 + x\sum_{n \geq 1} a_{n-1}x^{n-1} +\sum_{n \geq 1} x^n = x \sum_{n \geq 0}a_nx^n + 1 + \sum_{n \geq 1}x^n = x A(x) + \frac{1}{1-x}. $ Now I get $A(x) = \frac{1}{(1-x)^2}$.

but I don't see the trick regarding the second one. I mean the first one was ok, cause I could work with the recursion. But what can I do here?

$ A(x) = \sum_{n \geq 0} a_nx^n = \sum_{n \geq 0} n^3x^n = ?.$

Answer 1

$$\sum_{m=0}^{\infty} x^n=\frac{1}{1-x}, ~|x|<1~~~~(1)$$ Differentiating both sides w,r,t, $x$, we get $$\sum_{n=0}^{\infty} n x^n =\frac{x}{(1-x)^2}~~~~~(2)$$ Again differentiating w.r.t $x$, we get $$\sum_{n=0}^{\infty}n^2 x^n = \frac{x(1+x)}{(1-x)^3}~~~~(3)$$ Similarly, the next differentiation gives $$\sum_{n=0}^{\infty} n^3 x^{n-1}=\frac{x^2+4x+1}{(1-x)^4}~~~~(4)$$ Hence, we get $$\sum_{n=0}^{\infty} n^3 x^{n}=\frac{x(x^2+4x+1)}{(1-x)^4}~~~~(5)$$ Finally RHS of (5) is nothing but the required generating function.

Answer 2

Hint Try to find instead the generating function for $n(n-1)(n-2)$. Then for $n(n-1)$ and for $n$.

Write $$n^3=n(n-1)(n-2)-\alpha n(n-1)-\beta n$$