TITLE: Unusual induction question
QUESTION [3 upvotes]: 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!

REPLY [6 votes]: 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.
{"set_name": "stack_exchange", "score": 3, "question_id": 2004477}