3

Prove that $1^n + 2^n + . . . + (n − 1)^n$ is divisible by n if n is odd.

I tried using induction. I finished the base case and then the assumption, but then I couldn't substitute in the assumption like other induction questions because the exponent was k+1 and not k... Really need help!

Gerard L.
  • 2,536

1 Answers1

6

HINT: If $n$ is odd, and $a$ and $b$ are integers, $a^n+b^n$ is a multiple of $a+b$:

$$a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}b^2-\ldots-ab^{n-2}+b^{n-1})\;.$$

Pair up the numbers $1,\ldots,n-1$ properly and apply this fact.

Brian M. Scott
  • 616,228
  • Still stuck and not sure how to do that... – Gerard L. Nov 08 '16 at 02:00
  • @Gerard: Try pairing $a=k$ with $b=n-k$. – Brian M. Scott Nov 08 '16 at 02:01
  • @GerardL. See that $(1^n+(n-1)^n)+(2^n+(n-2)^n)+\dots$ and each pair has a factor. The first factor is $(1+(n-1))$, the second is $(2+(n-2))$, the third is... – Simply Beautiful Art Nov 08 '16 at 02:02
  • Still don't get it... – Gerard L. Nov 08 '16 at 02:13
  • @Gerard: A sum of multiples of $n$ is a multiple of $n$, and $k^n+(n-k)^n$ is a multiple of $k+(n-k)$, ... – Brian M. Scott Nov 08 '16 at 02:17
  • Is there just a quick way to get rid of the 1 and then use that to create the expression in the assumption and then substitute? I'm really stuck. – Gerard L. Nov 08 '16 at 02:51
  • @Gerard: You don’t want to get rid of the $1$; you want to pair it with $n-1$. $1^n+(n-1)^n$ is a multiple of $1+(n-1)=n$. $2^n+(n-2)^n$ is a multiple of $2+(n-2)=n$. $3^n+(n-3)^n$ is a multiple of $3+(n-3)=n$. $n$ is odd, so $n=2m+1$ for some $m$. If you keep going in this fashion, eventually you’ll reach $m^n+(n-m)^n$, which is a multiple of $m+(n-m)=n$. And since $n-m=(2m+1)-m=m+1$, this is the last pair. We have $m$ pairs, from $1^n+(n-1)^n$ through $m^n+(n-m)^n$, each of which is a multiple of $n$, so their sum is a multiple of $n$, and that’s exactly what you’re trying to show. – Brian M. Scott Nov 08 '16 at 09:09