# Using generating functions find the sum $1^3 + 2^3 + 3^3 +\dotsb+ n^3$

I am quite new to generating functions concept and I am really finding it difficult to know how to approach problems like this. I need to find the sum of $1^3 + 2^3 + 3^3 +\dotsb+ n^3$ using generating functions. How do I proceed about it?

-
If you have a generating function $f(x)$ for a sequence $a_n$, then $xf'(x)$ gives a generating function for $na_n$. Can you produce a generating function for $a_k = k^3$ (for $k \le n$) this way? –  Thomas Belulovich Oct 8 '12 at 15:01
The other element of the puzzle: from the generating function for the sequence $a_n$, do you understand how to find the generating function for the sequence $b_n=\sum_{i\leq n}a_i$? (Hint: if $g(x) = \sum_n b_nx^n$, what is $xg(x)$? What is $xg(x)-g(x)$? ) –  Steven Stadnicki Oct 8 '12 at 15:46

Let $s_n=\sum_{k=0}^nk^3$; your generating function for these numbers will be $$f(x)=\sum_{n\ge 0}s_nx^n\;.$$

You know that the sequence satisfies the recurrence $s_n=s_{n-1}+n^3$. Multiply this recurrence by $x^n$ and sum over $n\ge 0$:

$$\sum_{n\ge 0}s_nx^n=\sum_{n\ge 0}s_{n-1}x^n+\sum_{n\ge 0}n^3x^n\tag{1}\;.$$

The lefthand side of $(1)$ is $f(x)$. We assume that $s_n=0$ for all $n<0$, so we can rewrite $(1)$ as $$f(x)=x\sum_{n\ge 0}s_{n-1}x^{n-1}+\sum_{n\ge 0}n^3x^n=x\sum_{n\ge 0}s_nx^n+\sum_{n\ge 0}n^3x^n=xf(x)+\sum_{n\ge 0}n^3x^n$$ and see that $$f(x)=\frac1{1-x}\sum_{n\ge 0}n^3x^n\;.\tag{2}$$

To deal with the summation in $(2)$, start with $$\frac1{1-x}=\sum_{n\ge 0}x^n\;.$$ Differentiate and multiply by $x$ to get $$\frac{x}{(1-x)^2}=\sum_{n\ge0}nx^n\;.$$ Repeat: $$\frac{x(1+x)}{(1-x)^3}=\sum_{n\ge0}n^2x^n\;.$$ And one more time: $$\frac{x(1+4x+x^2)}{(1-x)^4}=\sum_{n\ge 0}n^3x^n\;.$$ Thus,

$$f(x)=\frac{x+4x^2+x^3}{(1-x)^5}\;.$$ Now decompose $f$ into partial fractions:

$$f(x)=-\frac1{(1-x)^2}+\frac7{(1-x)^3}-\frac{12}{(1-x)^4}+\frac6{(1-x)^5}\;.$$

Finally, you need to know some standard generating functions. In particular, you need to know that $$\frac1{(1-x)^k}=\sum_{n\ge 0}\binom{n+k-1}{k-1}x^n\;.$$ With that you get finally that

\begin{align*} f(x)&=\sum_{n\ge 0}\left(-\binom{n+1}1+7\binom{n+2}2-12\binom{n+3}3+6\binom{n+4}4\right)x^n\\ &=\sum_{n\ge 0}\frac14\left(n^4+n^3+n^2\right)x^n \end{align*}

and therefore that $$s_n=\frac14\left(n^4+2n^3+n^2\right)=\left(\frac{n(n+1)}2\right)^2\;.$$

-
Nice post. I believe there is a typo on the line "Thus, $f(x)=...$". The denominator should be $(1-x)^5$. –  Jonathan Oct 8 '12 at 16:23
@Jonathan: Thanks. You’re absolutely right. –  Brian M. Scott Oct 8 '12 at 16:26
Perhaps it would be good, to make that nice (+1) derivation easier memorizable, using the incidence, that the occuring coefficients (1,4,1) are Eulerian numbers and (1,7,12,6) are $(0! \cdot 1, 1! \cdot 7, 2!\cdot 6, 3!\cdot 1)$ and thus simple scalings of the Stirling numbers 2'nd kind. Knowing this, one can simply gain the coefficients for problem-variations, where the exponent of the initial sequence varies... –  Gottfried Helms Oct 8 '12 at 17:59
Thanks Brian for the beautiful solution. You made it absolutely clear. :) –  user1631009 Oct 10 '12 at 15:14
@user1631009: You’re welcome. –  Brian M. Scott Oct 11 '12 at 2:21

You can do this more prettily with exponential generating functions. Note that $$e^{kx} = \sum_n \frac{k^n x^n}{n!}$$ so $$1+e^x+e^{2x} + e^{3x} + \cdots + e^{kx} = \sum_n \frac{(1+2^n+3^n + \cdots + k^n) x^n}{n!}.$$ The left hand side is $$(e^{kx}-1) \cdot \frac{1}{e^x-1} = \left( kx + \frac{k^2 x^2}{2} + \frac{k^3 x^3}{6} + \cdots \right) \left( \frac{1}{x} - \frac{1}{2} + \frac{x}{12} - \frac{x^3}{720} + \cdots \right)$$ where the second factor can be expressed in terms of Bernoulli numbers.

Now compare coefficients of $x^3$ on both sides.

-
Notice that $k^{3}=\frac{1}{4}[k^{2}(k+1)^{2}-(k-1)^{2}k^{2}]$, so
$$\sum_{k=1}^{n}k^{3} =\frac{1}{4}\sum_{k=1}^{n}[k^{2}(k+1)^{2}-(k-1)^{2}k^{2}] =\frac{1}{4}n^{2}(n+1)^{2}$$