Another sweetener problem in Number Theory for RMO

II picked the following problem from Professor Titu Andreescu’s literature).

Let k be an odd positive integer. Prove that

$(1+2+\ldots+n)|(1^{k}+2^{k}+\ldots+n^{k})$ for all positive integers n.

Proof:

We consider two cases:

Case I: In the first case, we assume that n is odd and write $n=2m+1$ . Then,

$1+2+\ldots+n=(m+1)(2m+1)$ . We have

$1^{k}+2^{k}+\ldots+n^{k}=1^{k}+2^{k}+\ldots+(2m+1)^{k}$ , which, in turn equals,

$[1^{k}+(2m+1)^{k}]+[2^{k}+(2m)^{k}]+\ldots+[m^{k}+(m+2)^{k}]+(m+1)^{k}$

Since k is odd, $(x+y)$ is a factor of $x^{k}+y^{k}$ . Hence, $2m+2$ divides $i^{k}+(2m+2-i)^{k}$ for $i=1, 2, \ldots, m$ . Consequently, $m+1$ divides $1^{k}+2^{k}+\ldots + n^{k}$ . Likewise, we have

$1^{k}+2^{k}+ \ldots + n^{k}=1^{k}+2^{k}+\ldots + (2m+1)^{k}$

which is equal to $[1^{k}+(2m)^{k}]+[2^{k}+(2m-1)^{k}]+\ldots+[m^{k}+(m+1)^{k}]+(2m+1)^{k}$

Hence, $(2m+1)$ divides $i^{k}+(2m+1-i)^{k}$ for $i=1, 2, \ldots, m$ . Consequently, $2m+1$ divides $1^{k}+2^{k}+\ldots+n^{k}$ . We have shown that each of $m+1$ and $(2m+1)$ divides $1^{k}+2^{k}+\ldots+n^{k}$ . Since $gcd(m+1, 2m+1)=1$ , we conclude that $(m+1)(2m+1)$ divides $1^{k}+2^{k}+\ldots+n^{k}$ .