<s>[INST] Showing that $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$ 
For any odd positive integer $k\geq1$, the sum $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$.

I used induction principle for the solution but cannot prove it.
I took $P(k) = 1^k+2^k+\dots+n^k$.
For $P(1)$ it is true.
For $P(n)$ let it be true.
But for $P(n+1)$ I cannot solve it.
 [/INST] As $k$ is odd, 
$r^k+(n+1-r)^k$ is divisible by $r+(n+1-r)=n+1$
and $s^k+(n-s)^k$ is divisible by $s+(n-s)=n$
Putting $r=1,2,\cdots,n-1,n$ and adding them we get
$$(n+1)|\sum_{1\le r\le n}\{r^k+(n+1-r)^k\}  \implies (n+1)|2\sum_{1\le r\le n}r^k$$
Putting $s=1,2,\cdots,n-1,n$ and adding them we get
$$n|\sum_{1\le s\le n}\{s^k+(n-s)^k\}  \implies (n)|2\sum_{1\le s\le n}s^k \implies n|2\sum_{1\le r\le n}r^k$$
Now, either $n$ or $n+1$ is odd
If $n$ is odd, $$n|2\sum_{1\le r\le n}r^k\implies n|\sum_{1\le r\le n}r^k$$
$$\implies \text{lcm}(n+1,n) | 2\sum_{1\le r\le n}r^k$$
$$\implies n(n+1) | 2\sum_{1\le r\le n}r^k\implies \frac{n(n+1)}2 | \sum_{1\le r\le n}r^k$$
Similarly when $n+1$ is odd
</s>