# Proof by induction that $\left(\sum_{k=1}^nk\right)^2\ge\sum_{k=1}^nk^2$

I am a bit new to logical induction, so I apologize if this question is a bit basic.

I tried proving this by induction:

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

Starting with the base case $n=1$:

$$1^2\ge1^2$$

Then to prove that $P(n)\to P(n+1)$:

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

Since they're both multiplied by $(n+1)^2$, it's easy to see that if $\left(\sum_{k=1}^nk\right)^2\ge\sum_{k=1}^nk^2$, then $(n+1)^2\left(\sum_{k=1}^nk\right)^2\ge(n+1)^2\sum_{k=1}^nk^2$. But if the $\ge$ were replaced with a $\le$, the proof would still be valid, even though it's demonstrably not true.

I can see that it would take strong induction would fix this problem, but if I didn't know by observation that $\left(\sum_{k=1}^nk\right)^2\le\sum_{k=1}^nk^2$ isn't true by observation, how would I know to use strong induction?

-
Make sure you understand the $\sum$ notation. $$(n+1)^2\left(\sum_{k=1}^nk\right)^2\neq \left(\sum_{k=1}^{n+1}k\right)^2$$ and $$(n+1)^2\sum_{k=1}^nk^2\neq \sum_{k=1}^{n+1}k^2.$$ – Zev Chonoles May 20 '13 at 20:11
@ZevChonoles Ah, I see what I did wrong now...stupid mistake. – Ataraxia May 20 '13 at 20:12
As a small note you've used $n$ to denote both the bound of your sum and as the index of your induction. – user47805 May 20 '13 at 20:17

You're not quite on the right track. Your base case is just fine. For your induction step, suppose that $$\left(\sum_{k=1}^nk\right)^2\ge\sum_{k=1}^nk^2.$$ Note then that $$\left(\sum_{k=1}^{n+1}k\right)^2=\left((n+1)+\sum_{k=0}^nk\right)^2=(n+1)^2+2(n+1)\sum_{k=1}^nk+\left(\sum_{k=1}^nk\right)^2$$ and that $$\sum_{k=1}^{n+1}k^2=(n+1)^2+\sum_{k=1}^nk^2.$$ Can you get the rest of the way from there?

Alternately, you can proceed directly, noting that \begin{align}\left(\sum_{k=1}^nk\right)^2 &= \left(\sum_{k=1}^nk\right)\left(\sum_{j=1}^nj\right)\\ &= \sum_{k=1}^nk\sum_{j=1}^nj\\ &= \sum_{k=1}^n\sum_{j=1}^njk\\ &= \sum_{k=1}^n\left(k^2+\underset{j\ne k}{\sum_{j=1,}^n}jk\right)\\ &= \sum_{k=1}^nk^2+\sum_{k=1}^n\underset{j\ne k}{\sum_{j=1,}^n}jk\\ &\ge \sum_{k=1}^nk^2.\end{align}

-

Hints:

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

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

-
...which are, themselves, proven by induction! – The Chaz 2.0 May 20 '13 at 20:32

$$\sum^n_1 k=1+2+ \dots n$$

$$(\sum^n_1 k)^2=(1+2+ \dots n)^2 \neq1^2+2^2 + \dots n^2$$

-
Not sure how this relates to the question being asked. – breeden Jan 7 '15 at 20:37
The text passage contains a mathematical question in the form of a proof by induction, but no explicit answer to the question is provided. The passage is a discussion of an attempted proof and a request for clarification on the use of induction.
single_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Proof by induction that $\left(\sum_{k=1}^nk\right)^2\ge\sum_{k=1}^nk^2$

I am a bit new to logical induction, so I apologize if this question is a bit basic.

I tried proving this by induction:

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

Starting with the base case $n=1$:

$$1^2\ge1^2$$

Then to prove that $P(n)\to P(n+1)$:

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

Since they're both multiplied by $(n+1)^2$, it's easy to see that if $\left(\sum_{k=1}^nk\right)^2\ge\sum_{k=1}^nk^2$, then $(n+1)^2\left(\sum_{k=1}^nk\right)^2\ge(n+1)^2\sum_{k=1}^nk^2$. But if the $\ge$ were replaced with a $\le$, the proof would still be valid, even though it's demonstrably not true.

I can see that it would take strong induction would fix this problem, but if I didn't know by observation that $\left(\sum_{k=1}^nk\right)^2\le\sum_{k=1}^nk^2$ isn't true by observation, how would I know to use strong induction?

-
Make sure you understand the $\sum$ notation. $$(n+1)^2\left(\sum_{k=1}^nk\right)^2\neq \left(\sum_{k=1}^{n+1}k\right)^2$$ and $$(n+1)^2\sum_{k=1}^nk^2\neq \sum_{k=1}^{n+1}k^2.$$ – Zev Chonoles May 20 '13 at 20:11
@ZevChonoles Ah, I see what I did wrong now...stupid mistake. – Ataraxia May 20 '13 at 20:12
As a small note you've used $n$ to denote both the bound of your sum and as the index of your induction. – user47805 May 20 '13 at 20:17

You're not quite on the right track. Your base case is just fine. For your induction step, suppose that $$\left(\sum_{k=1}^nk\right)^2\ge\sum_{k=1}^nk^2.$$ Note then that $$\left(\sum_{k=1}^{n+1}k\right)^2=\left((n+1)+\sum_{k=0}^nk\right)^2=(n+1)^2+2(n+1)\sum_{k=1}^nk+\left(\sum_{k=1}^nk\right)^2$$ and that $$\sum_{k=1}^{n+1}k^2=(n+1)^2+\sum_{k=1}^nk^2.$$ Can you get the rest of the way from there?

Alternately, you can proceed directly, noting that \begin{align}\left(\sum_{k=1}^nk\right)^2 &= \left(\sum_{k=1}^nk\right)\left(\sum_{j=1}^nj\right)\\ &= \sum_{k=1}^nk\sum_{j=1}^nj\\ &= \sum_{k=1}^n\sum_{j=1}^njk\\ &= \sum_{k=1}^n\left(k^2+\underset{j\ne k}{\sum_{j=1,}^n}jk\right)\\ &= \sum_{k=1}^nk^2+\sum_{k=1}^n\underset{j\ne k}{\sum_{j=1,}^n}jk\\ &\ge \sum_{k=1}^nk^2.\end{align}

-

Hints:

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

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

-
...which are, themselves, proven by induction! – The Chaz 2.0 May 20 '13 at 20:32

$$\sum^n_1 k=1+2+ \dots n$$

$$(\sum^n_1 k)^2=(1+2+ \dots n)^2 \neq1^2+2^2 + \dots n^2$$

-
Not sure how this relates to the question being asked. – breeden Jan 7 '15 at 20:37
user
The text passage contains a mathematical question in the form of a proof by induction, but no explicit answer to the question is provided. The passage is a discussion of an attempted proof and a request for clarification on the use of induction.

TYPE: SINGLE_QUESTION