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

  • 3
    $\begingroup$ Great answer! :) $\endgroup$ – abc... Jun 18 '18 at 5:04
  • $\begingroup$ I still dont get it can u explain ? $\endgroup$ – Randin Jun 19 '18 at 5:01
  • $\begingroup$ @RandinMichaelDivelbiss $1^n \equiv -(n-1)^n \pmod {n^2}$, $2^n \equiv -(n-2)^n \pmod {n^2}$, and so on, because $n$ is odd, and because $(n-k)^n = (\text{terms having n with power }\ge 2) + (-1)^{n-1}n^2k^{n-1} + (-1)^nk^n$, due to which only the last term remains. So, all such pairs cancel out and only $n^n \pmod {n^2}$ is left, which is $0$. $\endgroup$ – GoodDeeds Jun 19 '18 at 5:10
  • $\begingroup$ Darn i still dont get it can u gmail me ? GoodDeeds12? $\endgroup$ – Randin Jun 19 '18 at 17:34
  • $\begingroup$ I got it ..should have posted this weeks ago ..right after i asked if u could email me it saw it ! 💡💡💡💡💡 $\endgroup$ – Randin Dec 20 '18 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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