How to determine equation for $\sum_{k=1}^n k^3$
Emily Wong 
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.
$\endgroup$ 510 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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. $$
$\endgroup$ 2 $\begingroup$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.)
$\endgroup$ 7 $\begingroup$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} $$
$\endgroup$ 3 $\begingroup$$$ \sum_{k=1}^nk^3=\bigg(\sum_{k=1}^n k\bigg)^2. $$ Can you get the intuition from the following two pictures?
The images are from Brian R Sears.
$\endgroup$ $\begingroup$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.
$\endgroup$ 1 $\begingroup$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.
$\endgroup$ 4 $\begingroup$One last Proof :
$$\sum_{k=1}^{n}k^{3}=1+8+27+64+...+n^{3}$$
$$\sum_{k=1}^{n}k^{3}=\underbrace{1}_{1^{3}}+\underbrace{3+5}_{2^{3}}+\underbrace{7+9+11}_{3^{3}}+\cdots+\underbrace{\left(n(n-1)+1\right)+\cdots+\left(n(n+1)-1\right)}_{n^{3}}$$
$$\sum_{k=1}^{n}k^{3}=1+3+5+\cdots+\left(n(n+1)-1\right)$$
Since $n(n+1) -1 $ is odd, then $n(n+1) -1 $ is the form $2k -1$
$$n(n+1) -1 = 2k -1 $$ $$n(n+1) = 2k $$ $$\underbrace{\frac{n}{2}(n+1)}_{\text{Arithmetic progression}} = k $$
$$\sum_{k=1}^{n}k^{3}=\underbrace{\underbrace{\underbrace{\underbrace{1}_{1^{2}}+3}_{2^{2}}+5}_{3^{2}}+\cdots+\left(n(n+1)-1\right)}_{ \left(\frac{n^{2}+n}{2}\right)^{2}}$$
$$\sum_{k=1}^{n}k^{3}=\left(\frac{n^{2}+n}{2}\right)^{2}=\frac{1}{4}n^2(n+1)^2$$
Note:
$\sum_{k=1}^{n}(2k-1)=1+3+5+7+9+...+2n-1=n^{2}$
$\endgroup$ $\begingroup$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}. $$
$\endgroup$ $\begingroup$If you know the teniest bit of calculus, the following method is quite easy to implement:
$$f(x,p)=a_px+p\int_0^xf(t,p-1)dt$$
$$a_p=1-p\int_0^1f(t,p-1)dt$$
$$f(x,0)=x$$
This recursive formula yields the formula $\sum_{k=1}^nk^p=f(n,p)$.
For example,
$$a_1=1-1\cdot\int_0^1t\,dt=1-\frac12=\color{purple}{\frac12}$$
$$f(x,1)=\color{purple}{\frac12}x+\int_0^xt\,dt=\color{#4455aa}{\frac12x+\frac12x^2}$$
$$a_2=1-2\cdot\int_0^1\color{#4455aa}{\frac12t+\frac12t^2}\,dt=1-\frac12-\frac13=\color{green}{\frac16}$$
$$f(x,2)=\color{green}{\frac16}x+2\cdot\int_0^x\color{#4455aa}{\frac12t+\frac12t^2}\,dt=\color{#aa4444}{\frac16x+\frac12x^2+\frac13x^3}$$
$$a_3=1-3\cdot\int_0^1\color{#aa4444}{\frac16t+\frac12t^2+\frac13t^3}\,dt=1-\frac14-\frac12-\frac14=0$$
$$f(x,3)=0x+3\cdot\int_0^x\color{#aa4444}{\frac16t+\frac12t^2+\frac13t^3}\,dt=\frac14x^2+\frac12x^3+\frac14x^4$$
$\endgroup$ 2$$\sum_{k=1}^nk^3=\frac14x^2+\frac12x^3+\frac14x^4$$
