inequality - Proof by induction that $left(sum_{k=1}^nkright)^2gesum_{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?

Answer

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