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

Case II: In the second case, we assume that n is even. The proof is similar to that of the first case. We leave it to the reader.

—-Nalin Pihwa

One thought on “Another sweetener problem in Number Theory for RMO”

This site uses Akismet to reduce spam. Learn how your comment data is processed.