Is it obvious intuitively that $1^p + 2^p + \cdots (n-1)^p$ is a polynomial in $n$?

Question

I am reading about Bernoulli function in "Calculus vol.1" by Matsusaburo Fujiwara(in Japanese).

The author proved that $$1^p + 2^p + \cdots (n-1)^p$$ is a polynomial in $n$ of degree $p+1$.

I understood the proof. In fact, it was an easy proof.

But I am not sure that it is obvious intuitively that $$1^p + 2^p + \cdots (n-1)^p$$ is a polynomial in $n$ or not.

The fact that the number of terms depends on $n$ is of concern to me. Notice also that the final sum is of degree $p+1$, not of degree $p$, and I would like an argument that accounts for that.

Answer 1

It is an obvious inductive (with respect to $p$) corollary of the binomial formula .

Answer 2

What seems true to me is "the sum of $n$ polynomials, $q_i(n)$, with degree($q_i) \le p$, is a polynomial in $n$ of degree at most $p+1$".

If I can prove this, then letting $q_i(n) = (n-i)^p$ we would have you statement (with the summation term written in the opposite order).

Answer 3

It sounds like you think the proof is not "obvious intuitively". The $\ldots$ are hard because they are not part of the system of what works and what doesn't. Expand it a little more $1^p+2^p+3^p+\ldots (n-2)^p+(n-1)^p$ and I think it is easy to see that if you do the full expansion that there is no term with a higher exponent than $n^p$, so it is a polynomial.

Added based on the edit: If the coefficient of the $n^p$ term grows with $n$, that becomes an $n^{p+1}$ term. That is still polynomial. The point is that it doesn't become exponential, which is a totally different order of growth.

Answer 4

This may be viewed as the consequence of the fact that the forward difference operator

$$ \Delta f(x) := f(x+1) - f(x) $$

maps a polynomial of degree $p$ into another polynomial of degree $p-1$. This observation itself is a direct consequence of the binomial theorem. Then your sum is kind of a reversal of this process, so it is not strange to expect that the sum $\sum_{k=1}^{n} k^{p-1}$ results in a polynomial in $n$ of degree $p$.

A similar line of reasoning applies, in a neater way, to integration and differentiation. Indeed,

$$ \int x^{p-1} \, \mathrm{d}x = \frac{x^p}{p} + C $$

for $p$ positive integer follows from the differentiation rule

$$ \frac{\mathrm{d}}{\mathrm{d}x} x^p = px^{p-1} $$

which itself is again a consequence of the binomial theorem.