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?
 A: 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.
A: 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}$$
A: 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+2n^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\;.$$
A: Note that if $A(z) = \sum_{n \ge 0} a_n z^n$, then
$$
z \frac{\mathrm{d}}{\mathrm{d} z} A(z)
  = \sum_{n \ge 0} n a_n z^n
$$
and also:
$$
\frac{A(z)}{1 - z}
  = \sum_{n \ge 0} \left( \sum_{0 \le k \le n} a_k \right) z^n
$$
Starting with:
$$
\sum_{n \ge 0} z^n
  = \frac{1}{1 - z}
$$
the generating function for the sum you want is:
$\begin{align}
 \frac{z}{1 - z}
   \frac{\mathrm{d}}{\mathrm{d} z}
     \left( z \frac{\mathrm{d}}{\mathrm{d} z}
       \left( z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \right)
     \right)
  &= \frac{z (1 + 4 z + z^2)}{(1 - z)^5}
\end{align}$
Thus:
$\begin{align}
\sum_{0 \le k \le n} k^3
  &= [z^n] \frac{z (1 + 4 z + z^2)}{(1 - z)^5} \\
  &= [z^n] (z + 4 z^2 + z^3) \sum_{k \ge 0} (-1)^k \binom{-5}{k} z^k \\
  &= [z^n] (z + 4 z^2 + z^3) \sum_{k \ge 0} \binom{k + 5 - 1}{5 - 1} z^k \\
  &= \binom{n - 1 + 4}{4}
        + 4 \binom{n - 2 + 4}{4}
        + \binom{n - 3 + 4}{4} \\
  &= \frac{n^2 (n + 1)^2}{4}
\end{align}$
Note that:
$$
\sum_{0 \le k \le n} k^3
  = \left( \sum_{0 \le k \le n} k \right)^2
$$
A: If you really want to get blown away, consider the following, taken from Aigner's "A Course in Enumeration" (Springer, 2007). Define:
$$
s_m(n) = \sum_{0 \le k < n} k^m
$$
and it's exponential generating function:
$
  \begin{align}
    \widehat{S}_n(z)
      &= \sum_{m \ge 0} s_m(n) \frac{z^m}{m!} \\
      &= \sum_{1 \le k \le n - 1} \sum_{m \ge 0} \frac{k^m z^m}{m!} \\
      &= \sum_{1 \le k \le n - 1} \mathrm{e}^{k z} \\
      &= \frac{\mathrm{e}^{n z} - 1}{\mathrm{e}^z - 1}
  \end{align}
$
This is almost the exponential generating function for the powers:
$
  \begin{align}
    \widehat{P}(z)
      &= \sum_{m \ge 0} n^m \frac{z^m}{m!} \\
      &= \mathrm{e}^{n z}
  \end{align}
$
Sadly, the series $\mathrm{e}^z - 1$ has no reciprocal, as it has no constant term. But we can write:
$$
    (\widehat{P}(z) - 1) \widehat{B}(z)
    = z \widehat{S}(z)
$$
where:
$$
    \widehat{B}(z)
      = \frac{z}{\mathrm{e}^z - 1}
$$
whose coefficients are the Bernoulli numbers:
$\begin{align}
    \widehat{B}(z)
      &= \sum_{n \ge 0} B_n \frac{z^n}{n!} \\
      &= 1 - \frac{1}{2} z + \frac{1}{6} \frac{z^2}{2!}
    - \frac{1}{30} \frac{z^4}{4!} + \frac{1}{42} \frac{z^6}{6!}
    - \frac{1}{30} \frac{z^8}{8!} + \frac{5}{66} \frac{z^{10}}{10!}
    - \frac{691}{2130} \frac{z^{12}}{12!}
    + \frac{7}{6} \frac{z^{14}}{14!}
    - \dotsb
\end{align}$
and finally:
$$
    \sum_{m \ge 0} s_m(n) \frac{z^{m + 1}}{m!}
      = \sum_{m \ge 0} z^m
   \sum_{0 \le k \le m}
     \binom{m}{k} \frac{(n z)^{m - k}}{(m - k)!} B_k
$$
Comparing coefficients of $z^{m + 1}$ and simplifying:
$$
    s_m(n)
      = \frac{1}{m + 1}
    \sum_{0 \le k \le m} (-1)^k \binom{m + 1}{k} B_k n^{m + 1 - k}
$$
A: Yet another way is to start with:
$$
\sum_{0 \le k \le n} z^k = \frac{1 - z^{n + 1}}{1 - z}
$$
differentiate thrice:
$$
\frac{\mathrm{d}}{\mathrm{d} z}
   \left( z \frac{\mathrm{d}}{\mathrm{d} z}       
     \left(
       z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1 - z^{n + 1}}{1 - z}
     \right)
   \right)
= \frac{1 + 4 z
          + z^2 
          - z^n (1 - 3 n^2 - n^3)
          - z^{n + 1} (4 - 6 n^2 - 3 n^3)
          - z^{n + 2} (1 - 3 n + 3 n^2 + 3 n^3)
          + z^{n + 3} n^3}
       {(1 - z)^4}
$$
Taking the limit as $z \to 1$ of this mess (l'Hôpital to the rescue) again gives:
$$
\sum_{0 \le k \le n} k^3 = \frac{n^2 (n + 1)^2}{4}
$$
The above courtesy of my CAS, maxima. Any transcription errors are mine only.
A: This is the particular case $p=3$ , more generally known as the Faulhaber formula which gives a closed-form for the sum $\sum_{k=1}^n k^p$
Some more proofs can be found here: p1,p2,p3
