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.

How do you find an algebraic formula for $\sum_{k=1}^n k^3$? I am able to find one for $\sum_{k=1}^n k^2$, but not $k^3$. Any hints would be appreciated.

share|improve this question
    
Do you want a method for deriving one, or are you content to have one? $$\sum_{k=1}^nk^3=\frac14n^2(n+1)^2\;.$$ –  Brian M. Scott Mar 5 '13 at 2:18
    
I'm looking for a method to derive it. –  AlexHeuman Mar 5 '13 at 2:19
    
There is always induction. Once you know the formula. And here are some more: math.com/tables/expansion/power.htm –  1015 Mar 5 '13 at 2:19
4  
I'm not sure what you mean by induction other than a proof. I'm looking for a way to obtain the formula without knowing it, not to prove it. –  AlexHeuman Mar 5 '13 at 2:21
    
math.stackexchange.com/q/61482/9464 –  Jack Mar 5 '13 at 3:01

8 Answers 8

up vote 13 down vote accepted

You can derive it from the formulas for the sums of lower powers:

$$\begin{align*} \sum_{k=1}^nk^3&=\sum_{k=1}^n\left(k\cdot k^2\right)\\ &=\sum_{k=1}^nk^2\sum_{i=1}^k1\\ &=\sum_{k=1}^n\sum_{i=1}^kk^2\\ &=\sum_{i=1}^n\sum_{k=i}^nk^2\\ &=\sum_{i=1}^n\left(\sum_{k=1}^nk^2-\sum_{k=1}^{i-1}k^2\right)\\ &=\sum_{i=1}^n\left(\frac16n(n+1)(2n+1)-\frac16i(i-1)(2i-3)\right)\\ &=\frac16n^2(n+1)(2n+1)-\frac16\sum_{i=1}^ni(i-1)(2i-3)\\ &=\frac16n^2(n+1)(2n+1)-\frac16\sum_{i=1}^n\left(2i^3-5i^2+3i\right)\\ &=\frac16n^2(n+1)(2n+1)+\frac56\sum_{i=1}^ni^2-\frac12\sum_{i=1}^ni-\frac13\sum_{i=1}^ni^3\\ &=\frac16n^2(n+1)(2n+1)+\frac5{36}n(n+1)(2n+1)-\frac14n(n+1)-\frac13\sum_{k=1}^nk^3\;, \end{align*}$$

and from here you can clearly solve for $\sum_{k=1}^nk^3$. Evidently this technique can be applied repeatedly, though it rapidly becomes very tedious.

Graham, Knuth, & Patashnik, Concrete Mathematics, offer many other approaches, including via finite calculus and generating functions.

Added (because I like it): The finite calculus approach requires first rewriting $k^3$ in terms of the falling factorials $k^{\underline1}=k$, $k^{\underline2}=k(k-1)=k^2-k$, and $k^{\underline3}=k(k-1)(k-2)=k^3-3k^2+2k$:

$$k^3=k^{\underline3}+3k^2+2k=k^{\underline3}+3k^{\underline2}+k^{\underline1}\;.$$

The coefficients are Stirling numbers of the second kind: in general $$x^n=\sum_{k=0}^n{n\brace k}x^{\underline k}\;.$$

Then

$$\begin{align*} \sum_{k=1}^nk^3&=\sum_{k=1}^n\left(k^{\underline3}+3k^{\underline2}+k^{\underline1}\right)\\ &=\left[\frac14k^{\underline4}+k^{\underline3}+\frac12k^{\underline2}\right]_1^{n+1}\\ &=\frac14n(n+1)(n-1)(n-2)+n(n+1)(n-1)+\frac12n(n+1)-0\\ &=\frac14n(n+1)\Big(n^2-3n+2+4(n-1)+2\Big)\\ &=\frac14n(n+1)\left(n^2+n\right)\\ &=\frac14n^2(n+1)^2\;. \end{align*}$$

There is a nice introduction to finite calculus in Section $2.6$ of Graham, Knuth, & Patashnik, Concrete Mathematics; Pete L. Clark has a handout with another introduction here.

share|improve this answer
    
Nice work, Brian, as usual! This one was fun! When I saw posts accumulating, I figured the OP would have more than enough to wade through than were I to add anything different (which would likely not have added much, anyway!) –  amWhy Mar 5 '13 at 3:12

Here is another approach,

$$ \sum_{k=1}^{n} (k+1)^4 - \sum_{k=1}^{n} k^4 = (n+1)^4-1 $$

$$ \implies 4\sum_{k=1}^{n}k^3 + 6\sum_{k=1}^{n} k^2 + 4\sum_{k=1}^{n}k + \sum_{k=1}^{n}1 = (n+1)^4 -1 $$

$$ \implies 4\sum_{k=1}^{n}k^3 = (n+1)^4-1-6\sum_{k=1}^{n}k^2 - 4\sum_{k=1}^{n}k - \sum_{k=1}^{n}1$$

$$ \implies \sum_{k=1}^{n}k^3 = \dots. $$

share|improve this answer
1  
Also, a great answer. –  AlexHeuman Mar 5 '13 at 2:49
    
@AlexHeuman: You are welcome. –  Mhenni Benghorbal Mar 5 '13 at 2:50

The general approach is to write $p(k)$ in terms of the polynomals $\binom{k}{i}$ with $i=0,1,2,\dots$

For example, $$k^3 = 6\binom k 3 + 6\binom k 2 + \binom k 1$$

Now, since $$\sum_{k=1}^{n} \binom{k}{i} = \binom{n+1}{i+1}$$

you get:

$$\sum_{k=1}^{n} k^3 =6\binom{n+1}{4} + 6\binom{n+1}{3} + \binom{n+1}{2}$$

(There is a slight problem above when $i=0$. You really need sums from $k=0$ to $n$ for that case. In all other cases, $k=0$ doesn't add anything.)

share|improve this answer
1  
Interesting approach. Had never seen it. –  Pedro Tamaroff Mar 5 '13 at 2:31
1  
Basically, for fixed $i$, the polynomial $\binom {k}{i}$ is a polynomial of degree $i$, and therefore they form a basis for all polynomials. –  Thomas Andrews Mar 5 '13 at 2:33
    
@ThomasAndrews I havne't yet encountered that notation. What is it? –  AlexHeuman Mar 5 '13 at 2:35
    
@AlexHeuman If you mean $\binom{k}{i}$, then it is defined as $$\binom{k}{i} = \frac{k(k-1)\cdots (k-(i-1))}{i\cdot (i-1)\cdots 2\cdot 1}$$ But if you are unfamiliar with this notation, this answer will probably not be much help. It is often called the "choose" function because it is the number of subsets of size $i$ in a set with $k$ elements. It is also sometimes called the binomial function –  Thomas Andrews Mar 5 '13 at 2:39
1  
@PeterTamaroff Actually, I sort of misremembered. It is even easier to use simple "falling factorials:" $$(k)_i = k(k-1)\cdots(k-(i-1)) = i!\binom{k}i$$ Then $$\sum_{k=0}^n (k)_i = \frac{1}{i+1}(n+1)_{i+1}$$ Then we have $$k^3 = (k)_3 + 3(k)_2 + (k)_1$$ yields the same result. –  Thomas Andrews Mar 5 '13 at 2:55

In addition to Brian M. Scott's answer, and the reference to $\mathit{Concrete \ Mathematics}$, you can actually derive this identity using $\mathit{higher}$ powers and perturbation method

Keep in mind that $$ \sum_{k=1}^{n}k=\frac{n(n+1)}{2}\\ \sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6} $$ So you start with $$ S_n=\sum_{k=1}^{n}k^4\\ S_{n+1}=S_n +(n+1)^4 = \sum_{k=1}^{n}(k+1)^4+1 =S_n+4 \sum_{k=1}^{n}k^3+6 \sum_{k=1}^{n}k^2 +4 \sum_{k=1}^{n}k +n+1 $$ hence $$ S_n +(n+1)^4=S_n+4 \sum_{k=1}^{n}k^3+6 \sum_{k=1}^{n}k^2 +4 \sum_{k=1}^{n}k +n+1 $$ So clearly the highest term cancels out and after some algebra you will get your $$ \sum_{k=1}^{n}k^3=\frac{(n(n+1))^2}{4} $$

share|improve this answer
1  
Thanks, this is also a great answer for me. –  AlexHeuman Mar 5 '13 at 2:49
    
You are welcome –  Alex Mar 5 '13 at 2:52
1  
You can use *asterisks* to italicise text outside of math mode. –  Rahul Mar 5 '13 at 6:30

The sum is $\dfrac{n^2(n+1)^2}{4}$.

The formula can be proved correct by induction. But there is also a nice geometric proof that can be found, for example, in the book Proofs Without Words.

For a general discussion of related problems, please see this Wikipedia aticle on Faulhaber's Formula.

Remark: There are various ways to discover the formula. We can calculate the sum of the first $n$ cubes for various small $n$. The actual formula is so simple that the answer leaps out. Then we can verify that itis correct by checking that $$\frac{(k^2)(k+1)^2}{4}-\frac{(k-1)^2(k^2)}{4}=k^3.$$ In this case, the calculation is instantaneous, for we are looking at a difference of squares.

Or else suppose we already know formulas for $\sum_1^n k$ and $\sum_1^n k^2$. Observe that $$(k+1)^4-k^4=4k^3+6k^2+4k+1.$$ Sum from $k=1$ to $k=n$. On the right we get a lot of cancellation, and we get $$(n+1)^4-1^4=4\sum_1^n k^3 +6\sum_1^n k^2+4\sum_1^n k +\sum_1^n 1.$$ We know everything in the equation above except $\sum_1^n k^3$. So now we know that too.

share|improve this answer
    
I'm not looking for a proof. I'm looking for the method to discover the algebraic equation. I'm not quite sure I understand how Faulhaber derived his formula. For instance, for $\sum_{k=1}^n k^2$ You can show that $(k+1)^3 - k^3 = 3k^2 + 3k + 1$ so $3[1^2 + 2^2 + ... + (n-1)^2] + 3[1 + 2 + ... + (n-1)] + n - 1 = n^3 - 1$ So by ruther manipulation we get $\sum_{k=1}^n k^2 = \frac {n^3} 3 + \frac {n^2} 2 + \frac n6$ –  AlexHeuman Mar 5 '13 at 2:31
1  
For the sum of the cubes, we can conjecture that the answer has shape $an^4+bn^3+cn^2+dn+e$. The formula should work for $n=0,1,2,3,4$. That gives $5$ equations in $5$ unknowns, really $4$ because we have immediately $e=0$. After we have found $a$ to $e$ that work for $0,1,2,3,4$, we can verify by induction that they work for all $n$. –  André Nicolas Mar 5 '13 at 2:35
    
Or else we can look at $(k+1)^4-k^4=4k^3+6k^2+6k+1$. Sum from $k=1$ to $n$. On the right, almost everything cancels. On the right, we get $4\sum k^3$ plus already known things. –  André Nicolas Mar 5 '13 at 2:39
    
thanks, I was trying to figure out a way from the same $(k+1)^3$ now that I knew the sum for $k^2$, but I couldn't so I should have put it to $(k+1)^4$ like you said. –  AlexHeuman Mar 5 '13 at 2:42

$$ \sum_{k=1}^nk^3=\bigg(\sum_{k=1}^n k\bigg)^2. $$ Can you get the intuition from the following two pictures?

enter image description here enter image description here

The images are from Brian R Sears.

share|improve this answer

One classic method is

$$\begin{align} \sum_{k=1}^{n} k^4 &= \left( \sum_{k=1}^n (k+1)^4 \right) + 1 - (n+1)^4 \\&= \left( \sum_{k=1}^n k^4 + 4 k^3 + 6 k^2 + 4 k + 1 \right) + 1 - (n+1)^4 \\&= \left( \sum_{k=1}^n k^4 \right) + 4 \left( \sum_{k=1}^n k^3 \right) + 6 \left( \sum_{k=1}^n k^2 \right) + 4 \left( \sum_{k=1}^n k^1 \right) + \left( \sum_{k=1}^n 1 \right) + 1 - (n+1)^4 \end{align}$$

The sum of fourth powers cancel out, and you can solve the equation for the sum of curves.


Another approach is to guess that the sum of cubes should be a fourth degree polynomial, then solve for the coefficients of the polynomial using the equations

  • $f(0) = 0$
  • $f(1) = 1$
  • $f(2) = 1 + 2^3$
  • $f(3) = 1 + 2^3 + 3^3$
  • $f(4) = 1 + 2^3 + 3^3 + 4^3$

Five equations in five unknowns. You can cut this down to 2 unknowns if you recognize some easy patterns: the leading coefficient for the sum of $n$-th powers is always $1/n$ and the next is always $1/2$, and the constant term is always 0.

share|improve this answer
    
+1 Recognizing that the sum should be a polynomial of degree $4$ since $\int x^3 dx = \frac{x^4}{4} + C$ seems the most straight-forward method for me here. It does involve finding a solution to a system of five equations in five unknowns, though as you note, the system is easily reduced to a manageable size. –  JavaMan Mar 5 '13 at 3:50

As you probably have already realized the formula $$ \sum_{k=1}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2 $$ can be proved using induction.

For $n=1$ you have $$ 1^3 = \left(\frac{1\cdot 2}{2}\right)^2. $$

Say that the formula holds for $n$ and prove that it holds for $n=1$. So you have/get $$ \sum_{k=1}^{n+1} k^3 = \left[\sum_{k=1}^n k^3\right] + (n+1)^3 = \frac{n^2(n+1)^2}{2^2} + (n+1)^3. $$ I will leave you to prove that this right hand side is indeed equal to $$ \frac{n^2(n+1)^2}{2^2} + (n+1)^3 = \dots = \frac{(n+1)^2(n+2)^2}{2^2}. $$

share|improve this answer

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.