Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 3 down vote accepted

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}$$

share|improve this answer

Hints:

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

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

share|improve this answer
    
...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$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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