Let $n$ be an odd positive integer. Show that the sum $1^n$ + $2^n$ + · · · + $n^n$ is divisible by $n^2$.
I tried induction on $n$ and thought of manipulating the terms by separating for example $3^{2n+3}$ into $3^{2n+1}\cdot 3^2$... then thought the sum of the squares of integers would play in to showing the inductive proof step for $n=2k+3$.
Using the binomial theorem, note that $k^n+(n-k)^n$ is congruent to $k^n+(-1)^nk^n$ modulo $n^2$, and since $n$ is odd, this is zero. Thus, pair off all terms, except the last one which is divisible by $n^2$.