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
  • 2
    $\begingroup$ Consider proving $n^2+n=\sum_{k=1}^n 2k$ again by induction. $\endgroup$
    – kingW3
    Commented Oct 29, 2017 at 12:44
  • $\begingroup$ Thank you. I will try this. $\endgroup$
    – Philipp
    Commented Oct 29, 2017 at 12:49

4 Answers 4

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
  • 1
    $\begingroup$ That's the quick answer I was looking for. (+1) $\endgroup$
    – Philipp
    Commented Oct 29, 2017 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$
2
  • $\begingroup$ Great Job! But what exactly do you depict as the "closed form"? $\endgroup$
    – Philipp
    Commented Oct 29, 2017 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$ Commented Oct 30, 2017 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .