0
$\begingroup$

usually the tasks look like

$$\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6}$$

or

$$\sum_{i=0}^n i^2 = i_1^2 + i_2^2 + i_3^2+...+i_n^2$$

But for the following task I have this form:

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

First I am a little confused by how I approach this. Do I transform them into a complete term like in the first example? Or can I do it by just using the sums themselves? And how should I treat the square of the sum best?

The first step is pretty straight forward creating the base case. But as soon as I get into doing the "Induction Step" I am getting stuck and not sure how to proceed.

I am looking to know best practice for this case.

Edit: This question is a little different, since it is expected to proove this only by using complete induction using the sum notation.

$\endgroup$
  • $\begingroup$ Can you show us how you start the induction step? $\endgroup$ – Bram28 Dec 9 '16 at 19:43
  • $\begingroup$ Well I am basically asking how to start off. But I can show you my first idea (leading to nothing) ($$\sum_{k=1}^n+1 k^2 = (k_1 + k_2 + k_3+...+k_n)²+(k_n+1_)²$$ $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 19:46
2
$\begingroup$

Assume that $\displaystyle\left(\sum_{k=1}^n k\right)^2 = \sum_{k=1}^nk^3$ holds for $n.$ We want to show that $\displaystyle\left(\sum_{k=1}^{n+1} k\right)^2 = \sum_{k=1}^{n+1}k^3.$ How to do it? Note that

$$\begin{align}\left(\sum_{k=1}^{n+1} k\right)^2&=\left(\sum_{k=1}^{n} k+n+1\right)^2\\&= \color{blue}{\left(\sum_{k=1}^{n} k\right)^2}+2(n+1)\sum_{k=1}^nk+(n+1)^2\\&\underbrace{=}_{\rm{induction}\:\rm{hypothesis}}\color{blue}{\sum_{k=1}^nk^3}+\color{red}{2(n+1)\sum_{k=1}^nk+(n+1)^2}\\&=\sum_{k=1}^{n+1}k^3\end{align}$$ if and only if $\displaystyle(n+1)^3=2(n+1)\sum_{k=1}^nk+(n+1)^2.$ Show this equality and you are done.

$\endgroup$
  • $\begingroup$ Thank you for this very complete and very insightful answer (and thanks to everybody else!!) I understand, that I still not understand enough about transforming sigma. Do you mind explaining a little how you get to the expression after the blue bracket? (...+2(n+1)....) $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 20:01
  • 2
    $\begingroup$ Let $\sum_{k=1}^n k = u$ then you want to expand $(u + (n+1))^2$ which is $u^2 + 2(n+1)u + (n+1)^2$. $\endgroup$ – Zain Patel Dec 9 '16 at 20:04
  • $\begingroup$ Thank you sir, I will spend now the rest of the night working this through. Thanks for this inspiration! $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 20:07
  • $\begingroup$ Awesome, I worked it out, thank you a lot, that was a very big help to me! $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 21:04
1
$\begingroup$

You could write $$\left( \sum_{k=1}^{n+1} k \right)^2 = \left[ \left(\sum_{k=1}^n k \right)+ (n+1) \right]^2 = \left(\sum_{k=1}^n k \right)^2 + 2(n+1) \left( \sum_{k=1}^n k\right) + (n+1)^2$$ The induction step assumes that the first term on the right is just $\displaystyle \sum_{k=1}^n k^3$. You need to show that the rest of the terms add up to $(n+1)^3$.

$\endgroup$
1
$\begingroup$

I'd do this is using induction to prove that $\sum_{k=1}^n k = \frac{n}{2}(n+1)$ and $\sum_{k=1}^n k^3 = \frac{n^2}{4}(n+1)^2$; these are straightforward induction proofs.

Then $$\left[\frac{n}{2}(n+1)\right]^2 = \frac{n^2}{4}(n+1)^2 \iff \left(\sum_{k=1}^n k\right)^2 = \sum_{k=1}^n k^3$$

$\endgroup$
  • $\begingroup$ Well, can i just use the n/2(n+1) as axiom though they are not given? $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 20:10
  • $\begingroup$ Perhaps, it's not too hard to prove without induction (just add the first n natural numbers to themselves in reverse and divide by 2) but I'd include it for the sake of completeness. (and it wouldn't be classified as an axiom, just a standard result) $\endgroup$ – Zain Patel Dec 9 '16 at 20:12
  • $\begingroup$ well the task expects me to prove it my complete induction, so I guess I got no choice here, but its a good mindbump to think about it :) $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 20:18
1
$\begingroup$

For the step you get:

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

$$[(\sum_{k=1}^n k) + (n+1)]^2 = $$

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

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

(inductive hypothesis)

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

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

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

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

$\endgroup$
  • $\begingroup$ so would you expect somebody to stay in the sumnotation doing the proof? $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 19:51
  • 1
    $\begingroup$ At first ... but then you can use the inductive hypothesis to replace the summation squared, and the single summation can be replaced by the n(n+1)/2 $\endgroup$ – Bram28 Dec 9 '16 at 19:53
  • $\begingroup$ Well I am not quite sure how our lecturer is going to evaluate this, but from seeing that highest rated answer at the top, I understand that its possible without leaving the sigma notation. If I'd go with n(n+1)/2 without having it as a theorem, I would expect it to have been proven. Note, we are just starting off with higher mathematics. $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 20:04
  • 1
    $\begingroup$ @ThomasChristopherDavies But you still need to show that last part ... for which you need the n(n+1)/2 $\endgroup$ – Bram28 Dec 9 '16 at 20:05
  • 1
    $\begingroup$ @ThomasChristopherDavies Cool! $\endgroup$ – Bram28 Dec 9 '16 at 21:32
1
$\begingroup$

I know you have to use induction, so this doesn't help you, but below is a cool proof by picture:

enter image description here

$\endgroup$
  • $\begingroup$ This is seriously super cool! thx for this great contribution! $\endgroup$ – Thomas Christopher Davies Dec 9 '16 at 22:10
  • 1
    $\begingroup$ @ThomasChristopherDavies Well, I wish I had come up with that myself :) But yeah, it's one of my favorite proof by pictures. $\endgroup$ – Bram28 Dec 9 '16 at 22:35

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