Proving $\sum_{k=1}^m{k^n}$ is divisible by $\sum_{k=1}^m{k}$ for $n=2013$

I got an interesting new question, it's about number theory and algebra precalculus. Here is the question:

a positive integer $n$ is called valid if $1^n+2^n+3^n+\dots+m^n$ is divisible by $1+2+3+\dots+m$ for every positive integer $m$.

1. Prove that 2013 is valid
2. Prove that there are infinite positive integers which are not valid

Every little hint, contribution and recommendation would be very helpful. Sorry for my bad english. Thanks before.

• Hint: $1^{2013}+n^{2013}$ is divisible by $n+1$. So is $2^{2013}+(n-1)^{2013}$ – Thomas Andrews Jun 3 '13 at 13:09
• Hint: tell us where you got the question. Then, tell us why it interests you. Then tell us what you have been able to do with it, and where you get stuck. – Gerry Myerson Jun 3 '13 at 13:16
• There aren't any infinite positive integers. You mean infinitely many different positive integers (each one finite). – Marc van Leeuwen Jun 3 '13 at 13:21

If $n$ is odd, then modulo $m+1$ we have $2(1^n + 2^n + \ldots + m^n) = (1^n+m^n) + (2^n+(m-1)^n) + \ldots + (m^n+1^n) \\ \equiv (1^n-1^n) + (2^n-2^n) + \ldots + (m^n-m^n) = 0 \pmod {m+1}$.

Also, since $m^n \equiv 0 \pmod m$, $2(1^n + 2^n + \ldots + m^n) \equiv 2(1^n + 2^n + \ldots + (m-1)^n) \equiv 0 \pmod m$

Since $m$ and $m+1$ are coprime, this shows that $2(1^n + \ldots + m^n)$ is a multiple of $m(m+1)$, and since $m(m+1)$ is even, $1^n + \ldots + m^n$ is a multiple of $m(m+1)/2 = 1+2+\ldots+m$.

If $n$ is even then $1+2^n \equiv 2 \pmod 3$, which is not a multiple of $1+2 = 3$

All odd $n$ are valid. In fact, for all odd $n$, $1^n + 2^n + 3^n + \dots + m^n$ is actually a polynomial in $1 + 2 + 3 + \dots + m = m(m+1)/2$. These polynomials are known as Faulhaber polynomials (see https://en.wikipedia.org/wiki/Faulhaber%27s_formula#Faulhaber_polynomials). You can find a proof of this fact in the AMM article "Sums of Powers of Integers" (modifying the proof slightly also shows the divisibility relation you want, but there are also easier ways to do this; see mercio's solution).

To answer your second question, all even $n$ are not valid; this can be easily seen by noticing that $2^n + 1$ is not divisible by $3$ if $n$ is even.

• Even knowing that the Faulhaber polynomials have zero coefficients in degree zero doesn't give you the result above, of course, since they have rational coefficients, so knowing about these polynomials still leaves something to argue. – Thomas Andrews Jun 3 '13 at 13:23
• Since the polynomials do not appear to have integer coefficients, it is not immediately clear to me why they would imply the divisibility condition. Could you explain that? – Marc van Leeuwen Jun 3 '13 at 13:24
• Good point; the fact that they are polynomials doesn't imply that they are divisble by 1 + 2 + 3 + ... + m (I guess I wasn't thinking when I posted this). Still, I think the same inductive proof can be used to show that this divisibility relation holds (but I admit the other proof is much nicer, if you only want the divisibility fact). – Jon Schneider Jun 3 '13 at 13:35

Use the binomial theorem to expand $\sum k^n$.

• Could you provide a bit more explanation of how to do that? It is not immediately apparent. – robjohn Jun 4 '13 at 13:31