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 = ?.$
Best Answer
$$\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.