Deriving Power Sums by Polynomial Interpolation

Most of us have seen these formulas: $$\sum_{i=k}^n k=1+2+\cdots+n=\dfrac{1}{2}n(n+1)\\ \sum_{i=k}^n k^2=1+4+\cdots+n^2=\dfrac{1}{6}n(n+1)(2n+1)\\ \sum_{i=k}^n k^3=1+8+\cdots+n^3=\dfrac{1}{4}n^2(n+1)^2\\ \sum_{i=k}^n k^4=1+16+\cdots+n^4=\dfrac{1}{30}n(n+1)(2n+1)(3n^2+3n-1).$$ These can be proved by mathematical induction, but we can actually derive them on our own!

We simply acknowledge the following fact: for any positive integer $p$, the power sum $\sum_{k=1}^n k^p$ can always be expressed as a polynomial $f(n)$ that has degree $p+1$ and has rational coefficients.

Let's try to derive the first and the last formula. For the first, let $f(n)=an^2+bn+c$. We have $f(1)=1,f(2)=3,f(3)=6$. We want to solve the linear system: $$a+b+c=1\\ 4a+2b+c=3\\ 9a+3b+c=6,$$ or equivalently in matrix form $$\begin{pmatrix}1&1&1\\ 4&2&1\\ 9&3&1\end{pmatrix}\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}1\\3\\6\end{pmatrix}.$$ Note that $$\begin{pmatrix}1&1&1\\ 4&2&1\\ 9&3&1\end{pmatrix}$$ is a Vandermonde matrix. Just type in vander([1 2 3])\[1;3;6] in Matlab and we have the solution: $a=1/2,b=1/2,c=0$.

For the last formula, let $f(n)=an^5+bn^4+cn^3+dn^2+en+f$. Then $f(1)=1,f(2)=17,f(3)=98,f(4)=354,f(5)=979,f(6)=2275$. Type vander([1 2 3 4 5 6]\[1;17;98;354;979;2275] in Matlab and we have $a=1/5, b=1/2, c=1/3, d=0, e=-1/30, f=0$. Finally, factor(1/5*x^5+1/2*x^4+1/3*x^3-1/30*x) gives the formula. The reader can also try to derive the formulas for $\sum_{i=k}^n k^5$ and $\sum_{i=k}^n k^6$.