2

What elementary proofs are there that $$\sum_{k=1}^{n}k^m$$ is always a degree $m+1$ polynomial?

It is well known that

$$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}$$

I'm interested in sums like this for $m\in\mathbb{N}$,

$$\sum_{k=1}^{n}k^m$$

If I know the solution is a polynomial of degree $m+1$, one of the ways I can derive this formula is by computing a small number of sums and solving the appropriate system of equations: \begin{align*} \sum_{k=1}^{1}k^2=1&=a(1)^3+b(1)^2+c(1)+d \\ 5&=a(2)^3+b(2)^2+c(2)+d \\ 14&=a(3)^3+b(3)^2+c(3)+d \\ 30&=a(4)^3+b(4)^2+c(4)+d \\ \end{align*}

Like this I can find that $a=\frac{1}{3}$, $b=\frac{1}{2}$, $c=\frac{1}{6}$, and $d=0$. Hence, $$\sum_{k=1}^{n}k^2=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}=\frac{n(n+1)(2n+1)}{6}$$ In fact, it is evident from integration power law rules that in general, $a=1/(m+1)$ so that the leading term is $n^{m+1}/(m+1)$. Once I have the formula like this, it is fairly trivial to prove it using induction.

The general solution to this problem is known, and Wolfram's MathWorld refers to it as Faulhaber's formula. However, beyond proving this formula, are there simple elementary proofs that show the solution will always be a degree $m+1$ polynomial, justifying that the above strategy will always work?

GPhys
  • 1,539
  • $(n+1)^m-n^m=?$ – John B Jan 19 '16 at 08:01
  • How would you prove the integration power law - by reversing the one for the derivative. Consider how you prove the derivative is what it is using binomial expansion (NB not the alternative way using the product rule for derivatives). If you do this properly you will see how the sum/integral relates to the differences/derivative and therefore how all the related pieces here come together. – Mark Bennet Jan 19 '16 at 08:34
  • Your sums should be written as $$\sum_{k=1}^n k^r\ .$$ – Christian Blatter Jan 19 '16 at 09:25
  • @MarkBennet I'd only ever proved the derivative power law with induction on the product rule. Thanks for bringing the other method to my attention. – GPhys Jan 19 '16 at 17:22
  • @ChristianBlatter Thanks, I fixed my notation abuse. – GPhys Jan 19 '16 at 18:29

1 Answers1

1

It is known that for $k=2,3$ $(\sum_{x=1}^{n} x^k) $ is a $k+1$ degree polynominal.

Assume by induction that the equation is true for all $j<k$.

Cosider following sum: $\sum_{x=1}^{n}[(x+1)^{k+1}-x^{k+1}] = 2^{k+1}-1^{k+1} +3^{k+1}-2^{k+1}+\ldots + (n+1)^{k+1}-n^{k+1} = (n+1)^{k+1}-1 $.

In other hand $\sum_{x=1}^{n}[(x+1)^{k+1}-x^{k+1}] = \sum_{x=1}^{n} \sum_{j=0}^{k+1}[{ {k+1}\choose j } x^j -x^{k+1}] = \sum_{x=1}^{n} \sum_{j=0}^{k}{ {k+1}\choose j } x^j = \sum_{j=0}^{k}{ {k+1}\choose j } \sum_{x=1}^{n} x^j $

Hence we have:

$ (n+1)^{k+1}-1= \sum_{j=0}^{k}{ {k+1}\choose j } \sum_{x=1}^{n} x^j$

$ (n+1)^{k+1}-1= { {k+1}\choose k } \sum_{x=1}^{n} x^k + \sum_{j=0}^{k-1}{ {k+1}\choose j } \sum_{x=1}^{n} x^j$

$ (n+1)^{k+1}-1= (k+1) (\sum_{x=1}^{n} x^k) + \sum_{j=1}^{k-1}{ {k+1}\choose j } (\sum_{x=1}^{n} x^j) + n$

From these equations, we know from mathematical induction that $(\sum_{x=1}^{n} x^k) $ will always be a degree k+1 polynominal.

Chad Shin
  • 2,132