 This is a Test of Mathematics Solution (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

## Problem

If k is an odd positive integer, prove that for any integer $\mathbf{ n ge 1 , 1^k + 2^k + \cdots + n^k }$ is divisible by $\mathbf{ \frac {n(n+1)}{2} }$

## Discussion

We write the given expression in two ways: $\mathbf{ S= 1^k + 2^k + \cdots + n^k }$ $\mathbf{ S =n^k + (n-1)^k + \cdots + 1^k }$

This implies $\mathbf{ 2S = (1^k + n^k ) + (2^k + (n-1)^k ) + \cdots + (n^k + 1^k) }$
Since k is odd, we know $\mathbf{ a^k + b^k = (a+b)(a^{k-1} - a^{k-2} b + \cdots + b^{k-1}) }$ , that is $\mathbf{ a+b}$ divides $\mathbf{a^k + b^k }$

Applying this to $\mathbf{ 2S = (1^k + n^k ) + (2^k + (n-1)^k ) + \cdots + (n^k + 1^k) }$ we have (n+1) divides $\mathbf{ 1^k + n^k }$ , $\mathbf{ (2 + n-1) =(n+1) }$ divides $\mathbf{(2^k + (n-1)^k)}$ and so on. Hence we can take n+1 common from each bracket, leading us to the following expression: $\mathbf{ 2S = (n+1)\times(\text{some constant}) \implies S = \frac{(n+1)}{2} \times(\text{some constant}) }$ . This implies $\mathbf{ \frac{(n+1)}{2} }$ divides S if n+1 is even, other wise n+1 divides S.

Now we show n (or n/2) divides S (when is odd or even respectively). To show this we write

S= $\mathbf{ 1^k + 2^k + \cdots + n^k }$ $\mathbf{ S =n^k + (n-1)^k + \cdots + 1^k }$

Again $\mathbf{ 2S =n^k + (1^k+ (n-1)^k) + (2^k + (n-2)^k) \cdots + ((n-1)^k + 1^k) + n^k }$
Since k is odd n divides $\mathbf{ a^k + (n-a)^k }$ for all a from 1 to n. Hence we can take n as common and have: $\mathbf{ 2S = (n)\times(\text{some constant}) \implies S = \frac{(n)}{2} \times(\text{some constant}) }$ . This implies $\mathbf{ \frac{(n)}{2} }$ divides S if n is even, other wise n divides S.

Now gcd of (n, n+1) = 1. Hence $\mathbf{ \frac{n(n+1)}{2} }$ divides S.

Proved