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.

For odd $k$ we have that
$$
a^k+b^k=(a+b)(a^{k-1}-a^{k-2}b+a^{k-3}b^2-\dots+b^{k-1})
$$
Thus, each column of
$$
\begin{align}
&0^k+\hphantom{(n-\ )}1^k+\hphantom{(n-\,\,)}2^k+\dots+n^k\\
&n^k+(n-1)^k+(n-2)^k+\cdots+0^k
\end{align}
$$
is divisible by $n$ and each column of
$$
\begin{align}
&1^k+\hphantom{(n-\ )}2^k+\hphantom{(n-\,\,)}3^k+\dots+n^k\\
&n^k+(n-1)^k+(n-2)^k+\cdots+1^k
\end{align}
$$
is divisible by $n+1$. Since $(n,n+1)=1$ we get that
$$
n(n+1)\,|\,2(1^k+2^k+3^k+\dots+n^k)
$$
and therefore, since $n(n+1)$ is even,
$$
\left.\frac{n(n+1)}{2}\middle|1^k+2^k+3^k+\dots+n^k\right.
$$
