Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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

3 Answers 3

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\;.$$

share|improve this answer
    
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.

share|improve this answer

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}$$

share|improve this answer
    
Thanks Alfred. Is there any way of solving this using generating functions? –  user1631009 Oct 8 '12 at 15:16
    
@user1631009: I'm sorry. Because the question is of discrete type, I don't know how to deal it using generating function. Why you persist on using generating functions to solve the problem? –  Alfred Chern Oct 8 '12 at 15:32
    
Interesting solution, even though it is not using generating functions. I wonder if similar approaches work for higher powers? –  Maesumi Oct 8 '12 at 17:16
    
@Maesumi: Yes, there exist similar approaches work for higher powers, but seems more complex. –  Alfred Chern Oct 8 '12 at 17:43
2  
I'm not trying to be rude Alfred, but I don't understand why an answer that doesn't even answer the question is getting upvotes. –  Graphth Oct 8 '12 at 19:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.