The most elementary proof of divisibility of sum of powers

Question

I am wondering how one can prove that for an arbitrary odd natural number $n$ and an arbitrary natural number $a$ the power-sum $S_{(a,n)}=1^n+2^n+\ldots +a^n $ is divisible by $S_{(a,1)}=1+2+\ldots + a$ in the most elementary way (possible) which comes to your mind. By an elementary way I mean the way which even middle school student could follow.

I traditionally tried to compute $S_{(a,n)}$ using the expansion of $(x-1)^{n+1}=\sum_{k=0}^{n+1}(-1)^k\binom{n+1}{k}x^{n+1-k}$.

I substituted $x=1,2,3,\ldots , a$ and then summed up results. After telescoping and cancelations I received $a^{n+1}=\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n+1}{k}S_{(a,n+1-k)}$, from which we can express $S_{(a,n)}$.

Nevertheless this approach seems to me tough and not so easy to follow for a middle school student; A loads of technical re-writing and quite long symbolic computations needed to go through.

My question: I am missing something very evident and elegant which gives the desired divisibility without tears?

Answer 1

Note that $r^n+(P-r)^n$ is divisible by $P$ by Binomial expansion and cancelling of the only terms without factors of $P$ (as $n$ is odd). If $a$ is odd, then all the terms in $S_{(a,n)}$ pair up in this way, with $P=a$, except for $a^n$, which is certainly a multiple of $a$, so $S_{(a,n)}$ is a multiple of $a$. If $a$ is even, then all the terms in $S_{(a,n)}$ pair up in this way, except for $a^n$ and $\Big(\dfrac{a}{2}\Big)^n$, so so $S_{(a,n)}$ is a multiple of $\dfrac{a}{2}$. We can make exactly the same argument with $P=a+1$, except that, if $a$ is odd, we find $S_{(a,n)}$ is a multiple of $\dfrac{a+1}{2}$ and if $a$ is even, $S_{(a,n)}$ is a multiple of $a+1$. Hence $S_{(a,n)}$ is always a multiple of $\dfrac{a(a+1)}{2}=S_{(a,1)}$.

Illustrative examples.

$1^n+2^n+3^n+4^n+5^n=(1^n+4^n)+(2^n+3^n) + 5^n$, so divisible by 5; also $1^n+2^n+3^n+4^n+5^n=(1^n+5^n)+(2^n+4^n) + 3^n$, so divisible by 3.

$1^n+2^n+3^n+4^n+5^n+6^n=(1^n+5^n)+(2^n+4^n) + 3^n +6^n$, so divisible by 3; also $1^n+2^n+3^n+4^n+5^n+6^n=(1^n+6^n)+(2^n+5^n) + (3^n+4^n)$, so divisible by 7.

Answer 2

I liked your approach by using binomial expansion.

Here is my approach using induction...

The base cases are obviously true.

Suppose $k$ is an odd natural number such that $S_{(a, 1)} \mid S_{(a, n)}$ for all odd $n\leq k-2$.

Observe that $$(p+1)^k+(p-1)^k=2 \sum_{m=0}^{\frac{k-1}{2}}\binom{k}{2m}p^{k-2m}$$ $$\therefore \sum_{p=1}^{a}[(p+1)^k+(p-1)^k]$$ $$=2\sum_{m=0}^{\frac{k-1}{2}}\binom{k}{2m}(1^{k-2m}+2^{k-2m}+...+a^{k-2m})$$ $$=2\sum_{m=0}^{\frac{k-1}{2}}\binom{k}{2m} S_{(a, k-2m) }$$ Now notice that, $(p+1)^k+(p-1)^k$ is divisible by $(p+1)+(p-1)=2p$ as $k$ is odd. $$\therefore \sum_{p=1}^{a}2p\, {\huge \mid} 2\sum_{m=0}^{\frac{k-1}{2}}\binom{k}{2m} S_{(a, k-2m)}=2S_{(a, k) }+2\sum_{m=1}^{\frac{k-1}{2}}\binom{k}{2m}S_{(a,\,k-2m)}$$ $$\implies\sum_{p=1}^{a}p\, {\huge \mid}\, S_{(a,\, k) }+\sum_{m=1}^{\frac{k-1}{2}}\binom{k}{2m}S_{(a,\,k-2m)}$$ $$\implies S_{(a, \,1)}\,{\huge \mid}\,S_{(a,\, k) }+\sum_{m=1}^{\frac{k-1}{2}}\binom{k}{2m}S_{(a,\,k-2m)} $$ $$\implies S_{(a, \,1)}\,{\huge \mid}\,S_{(a,\, k) }$$ $$[\because S_{(a, \,1)} \,\text{divides}\,S_{(a,\,k-2m)}\,\text{for all}\, 1\leq m\leq \frac{k-1}{2}]$$ Hence, by the principle of mathematical induction, we can conclude that $S_{(a, \, k) }$ is divisible by $S_{(a, \, 1) }$ for all odd $k$.