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.

Solution 1:

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. $$

Solution 2:

Let $\Pi_n$ be the vector space of polynomials with real coefficients and degree $\le n$. Consider the map $\Delta: \Pi_{k+1} \to \Pi_{k}$ given by $(\Delta P)(x) = P(x+1)-P(x)$. This is a linear map from an $k+2$-dimensional vector space to a $k+1$-dimensional vector space with a $1$-dimensional kernel consisting exactly of the constant functions. Hence, by the rank-nullity-theorem $\Delta$ is surjective. Thus there is a $Q \in \Pi_{k+1}$ such that $Q(x+1)-Q(x)=(x+1)^k$. Define $P(x)=Q(x)-Q(0)$. Then for each $n \in \Bbb N$:

$$P(n)=Q(n)-Q(0)=n^k+Q(n-1)-Q(0)=n^k+(n-1)^k+Q(n-1)+Q(0)=\ldots=n^k+(n-1)^k+ \ldots +1^k+Q(0)-Q(0)=n^k+(n-1)^k+\ldots+1^k$$.

Since $P(0)=P(-1)=0$, $X$ and $X+1$ divide $P(X)$, $X(X+1)|P(X)$. Hence $P(n)/(n(n+1))$ is a rational whose denominator can be assumed to have a fixed value $q$. On the other hand, choosing $n$ so large that $n(n+1)$ has only the divisor 2 smaller than $q$,you see that the denominator of $P(n)/(n(n+1))$ must be $2$ hence it must always be $2$ or $1$ and $n(n+1)/2|P(n)$.