9
$\begingroup$

This is a problem from Terence Tao's Solving mathematical problems, a personal perspective. The problem is:

Let $k,n\in\mathbb{N}$ with $k$ odd. Prove that the sum $1^k+2^k+\cdots+n^k$ is divisible by $1+2+\cdots+n$.

Here is the text's solution. However, I thought that the second modulus congruence that goes on like:

$1^k+2^k+3^k+\cdots+(m-1)^k+0^k +1^k+\cdots+(m-1)^k + 0\pmod m$."

Could be simplified as

$1^k+2^k+3^k+\cdots+(m-1)^k+0^k+(-(m-1))^k+\cdots+(-1)^k+0 \pmod m$ Now since $k$ is odd, $(-1)^k$ has to be $-1$. Similarly, $(-(m-1))^k$ has to be $-(m-1)^k$. Therefore, the first $m-1$ terms cancel with the last $m-1$ terms.

$\endgroup$
3

1 Answer 1

8
$\begingroup$

I'll show a simpler method than modular arithmetic.

Denote the first sequence $S_k = 1^k + 2^k + \cdots + n^k$.

Now the key step lies in seeing that $$1 + 2 + \cdots + n = \dfrac{n(n + 1)}2$$ (can you prove why)?

So we want to prove that $(n^2 + n) \mid 2S_k$, so we only need to show that $n \mid 2S_k$ and $(n + 1) \mid 2S_k$.

So rewrite $$2S_k = (1 + n^k) + (2^k + (n - 1)^k) + \cdots + (n^k + 1)$$ which is divisible by $n+1$ and $$2S_k=2n^k+(1+(n-1)^k)+(2^k+(n-2)^k)+\cdots+((n-1)^k+1)$$ which is divisible by $n$.

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .