On the sum of $k$-th powers in terms of earlier sums

Abstract

For $k$ a positive integer let $S_k(n)=1^k+2^k+\cdots +n^k$, i.e., $S_k(n)$ is the sum of the first $k$-th powers. Faulhaber conjectured (later proved by Jacobi) that for $k$ odd, $S_k(n)$ could be written as a polynomial of $S_1(n)$; for example $S_3(n)=S_1(n{)}^2$. We extend this result and prove that for any $k$ there is a polynomial $g_k(x,y)$ such that $S_k(n)=g(S_1(n),S_2(n))$. The proof yields a recursive formula to evaluate $S_k(n)$ as a polynomial of $n$ that has roughly half the number of terms as the classical one.

Version 2.0, 5 pages