**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**