If k is an odd positive integer, prove that for any integer $n≥1$ , $1^k+2^k+3^k+.....+n^k$ is divisible by $\frac {n(n+1)}2$
If k equals to 1, then it is an obvious case. Though the expression is seen to be true for $k=1$ , I could not prove it by induction, as the sum becomes too complex, according to what I did.. So I tried to prove that $1^k+n^k$ is congruent to $ 0(mod (n+1))$. That took me some far, but I could not come to a satisfactory conclusion.. Can anyone please help me with this? I feel there is a smarter approach to this one. Thank you..
Hint : Distinguish the cases $n$ even and $n$ odd and use $$(n-j)^k \equiv -j^k \mod n$$ and analogue for $\ n+1\ $ which allows you to delete all summands except possibly one. This way you can show that the sum is divisible by both $\frac{n}{2}$ and $n+1$ or both $\frac{n+1}{2}$ and $n$ depending on the parity of $n$. The claim then follows because $n$ and $n+1$ are coprime.