6
$\begingroup$

I am trying to prove $$\sum_{k=1}^nk^3=\sum_{k=1}^n\sum_{j=1}^nk\cdot j$$ by using induction. Alternative approaches to this problem are possible as well.

My thoughts so far:

$\sum_{k=1}^{n+1}k^3=\sum_{k=1}^{n+1}\sum_{j=1}^{n+1}k\cdot j$

$\Rightarrow\sum_{k=1}^nk^3+\left(n+1\right)^3=\sum_{k=1}^{n+1}k\cdot\sum_{j=1}^{n+1}j=\left(\sum_{k=1}^nk+n+1\right)\cdot\left(\sum_{j=1}^nj+n+1\right)$

$\Rightarrow\left(n+1\right)^3=\left(n+1\right)^2+\left(n+1\right)\cdot\left(\sum_{k=1}^nk+\sum_{j=1}^nj\right) $

$\Rightarrow \left(n+1\right)^2=\left(n+1\right)^{ }+\sum_{k=1}^n2k$

$\Rightarrow n^2+n=\sum_{k=1}^n2k$

This is where I am stuck. How can I continue from here? I read something about geometric progressions; do they apply to this example?

Any help is appreciated.

Philipp

$\endgroup$
  • 2
    $\begingroup$ Consider proving $n^2+n=\sum_{k=1}^n 2k$ again by induction. $\endgroup$ – kingW3 Oct 29 '17 at 12:44
  • $\begingroup$ Thank you. I will try this. $\endgroup$ – Philipp Oct 29 '17 at 12:49
2
$\begingroup$

You're almost done. To conclude simply note that \begin{align*} 2\sum_{k=1}^nk&=({\color{red}1}+{\color{blue}2}+\ldots+{\color{green}n})+({\color{red}n}+{\color{blue}{n-1}}+\ldots+{\color{green}1}) \\ &=({\color{red}1}+{\color{red}n})+({\color{blue}2}+{\color{blue}{n-1}})+\ldots + ({\color{green}n}+{\color{green}1})\\ &=n(n+1)\end{align*}

$\endgroup$
  • 1
    $\begingroup$ That's the quick answer I was looking for. (+1) $\endgroup$ – Philipp Oct 29 '17 at 20:57
2
$\begingroup$

By Induction

Per solution here, RHS=$\dfrac {n^2(n+1)^2}4$.

Proposition: $$\sum_{k=1}^n k^3=\sum_{k=1}^n\sum_{j=1}^n k\cdot j=\frac {n^2(n+1)^2}4$$

Induction:

Assume true for $n$.

For $n+1$:

$$\sum_{k=1}^{n+1}k^3=\frac {n^2(n+1)^2}4+(n+1)^3=\frac {(n+1)^2}4\left(n^2+4(n+1)\right)=\frac {(n+1)^2(n+2)^2}4$$ i.e. also true for $n+1$.

Clearly proposition is true for $n=1$.

Hence, by induction, the proposition is true for all positive integer $n$.


Direct Proof (Without using closed-form result)

This is a rather neat approach - a direct proof without having to work out the closed form. It is due to Misha Lavrov's answer to a question I asked.

$$\begin{align} \sum_{k=1}^n k^3 &=\sum_{k=1}^n\sum_{j=1}^k k^2\\ &=\sum_{k=1}^n\sum_{j=1}^k k(j+(k-j))\\ &=\sum_{k=1}^n\left[\sum_{j=1}^k kj+\sum_{j=1}^k k(k-j)\right]\\ &=\sum_{k=1}^n\left[\sum_{j=1}^k kj+\sum_{i=0}^{k-1} ki\right] &&\scriptsize(i=k-j)\\ &=\sum_{k=1}^n\left[\sum_{j=1}^k kj+\sum_{i=1}^{k-1} ki\right] &&\scriptsize (ki=0\text{ when }i=0)\\ &=\sum_{k=1}^n\left[\sum_{j=1}^k kj+\sum_{j=1}^{k-1} kj\right] &&\scriptsize\text{(using $j$ instead of $i$)}\\ &=\sum_{k=1}^n\sum_{j=1}^k kj+\sum_{j=1}^n\sum_{k=1}^{j-1}kj &&\scriptsize\text{(swapping $j,k$ in second term)}\\ &=\sum_{k=1}^n\sum_{j=1}^k kj+\sum_{k=1}^n\sum_{j=k+1}^{n}kj &&\scriptsize(1\le k<j\le n)\\ &=\sum_{k=1}^n\left(\sum_{j=1}^k kj+\sum_{j=k+1}^{n}kj\right)\\ &=\sum_{k=1}^n \sum_{j=1}^n kj\\ &=\sum_{k=1}^n k\sum_{j=1}^n j\\ &=\left(\sum_{k=1}^n k\right)^2\end{align}$$

$\endgroup$
  • $\begingroup$ Great Job! But what exactly do you depict as the "closed form"? $\endgroup$ – Philipp Oct 29 '17 at 20:59
  • 1
    $\begingroup$ @PhilippWulff - Thanks! The "closed form" is the answer without summation signs, which in this case is $\dfrac {n^2(n+1)^2}4$. $\endgroup$ – hypergeometric Oct 30 '17 at 0:59
1
$\begingroup$

One can prove $ n^2+n=\sum_{k=1}^n2k$

aganin by induction.

$$\sum_{k=1}^{n+1}2k=n^2+n+2n+2$$

$$\sum_{k=1}^{n+1}2k=n^2+2n+1+n+1$$

$$\sum_{k=1}^{n+1}2k=\left(n+1\right)^2+n+1$$

This statement $B(n)$ is valid for all $n\in\mathbb{N}$. Therefore, the first stament $A(n)$ must also be valid for all $n\in\mathbb{N}$.

$\endgroup$
1
$\begingroup$

For the value of $\sum k$ consider the following.

Starting with $$\sum_{k=1}^{n} x^{k} = \frac{x(1-x^{n})}{1-x}$$ and take a derivative to obtain $$\sum_{k=1}^{n} k \, x^{k} = \frac{x}{(1-x)^{2}} \, (1 - (n+1) \, x^{n} + n \, x^{n+1})$$ and then use L'Hospital's rule to obtain $$\sum_{k=1}^{n} k = \binom{n+1}{2}.$$

From here it can be shown that $$\sum_{k=1}^{n} k^{3} = \frac{n^{2}(n+1)^{2}}{4} = \binom{n+1}{2}^{2} = \left(\sum_{k=1}^{n} k \right)^{2}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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