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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s