The most elementary proof of divisibility of sum of powers 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?
 A: 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.
A: 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$.
