text: # 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