2026-11-07
In this manuscript, we derive closed formulas for multifold sums of powers of integers by combining the forward Newton interpolation formula with hockey-stick identities for binomial coefficients. We further obtain representations of multifold sums of powers in terms of Stirling numbers of the second kind and Eulerian numbers. Finally, we provide Wolfram Mathematica programs for the efficient verification of the derived identities.
This section introduces several lemmas, definitions, and conventions that we use in the main results. We use the notation for multifold sums introduced by Donald Knuth in (Knuth 1993).
Definition 1 (Multifold Sums of Powers). For non-negative integers \(r\), \(n\), and \(m\), we define multifold sums of powers by \[\begin{align*} \Sigma^{0}\,{n}^{m} &= n^m, \\ \Sigma^{1}\,{n}^{m} &= \Sigma^{0}\,{1}^{m} + \Sigma^{0}\,{2}^{m} + \cdots + \Sigma^{0}\,{n}^{m}, \\ \Sigma^{r+1}\,{n}^{m} &= \Sigma^{r}\,{1}^{m} + \Sigma^{r}\,{2}^{m} + \cdots + \Sigma^{r}\,{n}^{m}. \end{align*}\]
We use the following notation for the falling factorial.
Definition 2 (Falling Factorials). For integers \(n\) and \(k\), \[\begin{align*} \left(n\right)_{k} = \begin{cases} 0, \quad & \mathrm{if \; } k < 0, \\ 1, \quad & \mathrm{if \; } k = 0, \\ \prod_{j=0}^{k-1} (n-j), \quad & \mathrm{if \; } k>0. \end{cases} \end{align*}\]
J. F. Steffensen discusses generalized factorials in (Steffensen 1933).
Lemma 3 (Forward Newton’s formula). Let \(f\colon \mathbb{Z} \to \mathbb{C}\) be a function and let \(t \in \mathbb{Z}\). For every \(n \in \mathbb{Z}\), \[\begin{align*} f(n) = \sum_{k=0}^{\infty} \frac{\left(n-t\right)_{k}}{k!} \Delta^{k} f(t) = \sum_{k=0}^{\infty} \binom{n-t}{k} \Delta^{k} f(t), \end{align*}\] where the \(k\)-th forward difference \(\Delta^{k} f(t)\) of \(f\) evaluated at \(t\) is defined by \[\begin{align*} \Delta^{k} f(t) = \mathop{\textstyle\sum}_{j=0}^{k} (-1)^{k-j} \tbinom{k}{j} f(t+j). \end{align*}\]
Proof. Newton introduced this formula in (Newton and Chittenden 1850). Steffensen expressed it in modern notation in (Steffensen, Johan Frederik 1927, sec. 2, Equation (19)). The identity \(\frac{\left(n-t\right)_{k}}{k!} = \tbinom{n-t}{k}\) gives the second expression. ◻
The power case follows directly from the preceding formula.
Lemma 4 (Forward Newton’s formula for powers). For non-negative integers \(n\) and \(m\) and an arbitrary integer \(t\), \[\begin{align*} n^m = \sum_{k=0}^{m} \binom{n-t}{k} \Delta^{k} t^m. \end{align*}\]
Proof. This is the special case of Lemma [lem:forward-newtons-formula] obtained by taking \(f(n)=n^m\). ◻
We next recall a generalized hockey-stick identity.
Lemma 5 (Generalized hockey-stick identity). For arbitrary integers \(a\), \(b\), and \(j\), \[\begin{align*} \sum_{k=a}^{b} \binom{k}{j} = \binom{b+1}{j+1} - \binom{a}{j+1}. \end{align*}\]
Proof. We have \(\mathop{\textstyle\sum}_{k=a}^{b} \tbinom{k}{j} = \tbinom{a}{j} + \tbinom{a+1}{j} + \cdots + \tbinom{b}{j} = \left( \mathop{\textstyle\sum}_{k=0}^{b} \tbinom{k}{j} \right) - \left( \mathop{\textstyle\sum}_{k=0}^{a-1} \tbinom{k}{j} \right)\). The hockey-stick identity \(\mathop{\textstyle\sum}_{k=0}^{n} \tbinom{k}{j} = \tbinom{n+1}{j+1}\) therefore gives \[\begin{align*} \mathop{\textstyle\sum}_{k=a}^{b} \tbinom{k}{j} = \left( \mathop{\textstyle\sum}_{k=0}^{b} \tbinom{k}{j} \right) - \left( \mathop{\textstyle\sum}_{k=0}^{a-1} \tbinom{k}{j} \right) = \tbinom{b+1}{j+1} - \tbinom{a}{j+1}. \end{align*}\] This proves the identity. ◻
The following specialization will be useful in deriving the main results.
Lemma 6 (Forward hockey-stick identity). For an integer \(n\geq1\) and arbitrary integers \(t\), \(k\), and \(r\), \[\begin{align*} \sum_{j=1}^{n} \binom{j-t+r}{k+r} = \binom{n-t+r+1}{k+r+1} - \binom{1-t+r}{k+r+1}. \end{align*}\]
Proof. Set \(a=1-t+r\) and \(b=n-t+1\) in Lemma [lem:generalized-hockey-stick-identity]. ◻
We also record a formula for multifold sums of zero powers.
Lemma 7 (Multifold sums of zero powers). For non-negative integers \(r\) and \(n\), \[\begin{align*} \Sigma^{r}\,{n}^{0} = \binom{r+n-1}{r}. \end{align*}\]
Proof.
When \(r=0\), the definition gives \(\Sigma^{0}\,{n}^{0} = 1\).
When \(r=1\), \(\Sigma^{1}\,{n}^{0} = \mathop{\textstyle\sum}_{k=1}^{n} 1 = \tbinom{n}{1}\).
When \(r=2\), \(\Sigma^{2}\,{n}^{0} = \mathop{\textstyle\sum}_{k=1}^{n} \tbinom{k}{1} = \tbinom{n+1}{2}\).
When \(r=3\), \(\Sigma^{3}\,{n}^{0} = \mathop{\textstyle\sum}_{k=1}^{n} \tbinom{k+1}{2} = \tbinom{n+2}{3}\).
For general \(r\), the recurrence and hockey-stick identity give \[\begin{align*} \Sigma^{r}\,{n}^{0} &= \mathop{\textstyle\sum}_{k=1}^{n} \Sigma^{r-1}\,{k}^{0} = \mathop{\textstyle\sum}_{k=1}^{n} \tbinom{k+r-2}{r-1} \\ &= \tbinom{r+n-1}{r}. \end{align*}\]
This proves the formula. ◻
The next lemma gives the upper-index negation identity for binomial coefficients.
Lemma 8 (Upper Binomial negation). For integers \(n\) and \(k\), \[\begin{align*} \binom{-n}{k} = (-1)^{k} \binom{k+n-1}{k}. \end{align*}\]
Proof. This identity is given in (Graham et al. 1994, 164, Equation (5.14)). ◻
Finally, we adopt the zero-power convention.
Convention 9 (Zero Powers). For every \(x\), \[\begin{align*} x^0 = 1. \end{align*}\]
Donald Knuth discusses the convention \(x^0=1\), including the case \(x=0\), in Concrete Mathematics (Graham et al. 1994, 162) and in (Knuth 1992).
This manuscript derives formulas for sums of powers by combining the forward Newton interpolation formula for powers in Lemma [lem:forward-newtons-formula-for-powers] with the hockey-stick identity in Lemma [lem:forward-hockey-stick-identity]. We implement the algorithm for finding closed forms for sums of powers of integers proposed in (Kolosov 2026, Algorithm (11.2)). More precisely, the main idea is to express Newton’s formula in binomial bases associated with different difference operators. The following formulas illustrate these representations. \[\begin{align*} \begin{cases} f(x) &= \sum_{k=0}^{\infty} \frac{(x-a)^{[k]}}{k!} \delta^{k} f(a) = \sum_{k=0}^{\infty} \frac{x-a}{k} \binom{x-a+\frac{k}{2}-1}{k-1} \delta^{k} f(a), \\ f(x) &= \sum_{k=0}^{\infty} \frac{\left(x-a\right)_{k}}{k!} \Delta^k f(a) = \sum_{k=0}^{\infty} \binom{x-a}{k} \Delta^k f(a), \\ f(x) &= \sum_{k=0}^{\infty} \frac{(x-a)^{\left(k\right)}}{k!} \nabla^k f(a) = \sum_{k=0}^{\infty} \binom{x-a+k-1}{k} \nabla^k f(a), \\ f(x) &= \sum_{k=0}^{\infty} \frac{(x-a)^k}{k!} \frac{\mathrm{d}^{k} f(a)}{\mathrm{d} x^{k}}. \end{cases} \end{align*}\] Each variation of Newton’s formula above has its own binomial basis: \[\begin{align*} \begin{cases} \frac{\left(x\right)_{n}}{n!} &= \frac{1}{n!} x(x-1)(x-2)\cdots(x-n+1) =\binom{x}{n}, \\ \frac{x^{\left(n\right)}}{n!} &= \frac{1}{n!} x(x+1)(x+2)\cdots(x+n-1) =\binom{x+n-1}{n}, \\ \frac{x^{[n]}}{n!} &= \frac{1}{n!} \left( n + \frac{k}{2} -1 \right)\left( n + \frac{k}{2} -2 \right) \cdots \left( n - \frac{k}{2} +1 \right) =\frac{x}{n} \binom{x+\frac{n}{2}-1}{n-1}. \end{cases} \end{align*}\] These representations allow us to combine Newton’s formula with hockey-stick identities to derive closed forms for sums of powers of integers. This manuscript focuses on these closed forms, using forward Newton’s formula and the hockey-stick identity in Lemma [lem:forward-hockey-stick-identity].
We begin with Lemma [lem:forward-newtons-formula-for-powers], which gives forward Newton interpolation for powers. The following example illustrates the formula. \[\begin{align*} n^3 &= 0 \tbinom{n-0}{0} + 1 \tbinom{n-0}{1} + 6 \tbinom{n-0}{2} + 6 \tbinom{n-0}{3}, \\ n^3 &= 1 \tbinom{n-1}{0} + 7 \tbinom{n-1}{1} + 12 \tbinom{n-1}{2} + 6 \tbinom{n-1}{3}, \\ n^3 &= 8 \tbinom{n-2}{0} + 19 \tbinom{n-2}{1} + 18 \tbinom{n-2}{2} + 6 \tbinom{n-2}{3}, \\ n^3 &= 27 \tbinom{n-3}{0} + 37 \tbinom{n-3}{1} + 24 \tbinom{n-3}{2} + 6 \tbinom{n-3}{3}. \end{align*}\]
We now derive a formula for sums of powers. \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{k=0}^{m} \left[ \sum_{j=1}^{n} \binom{j-t}{k} \right] \Delta^{k} t^m. \end{align*}\] Setting \(r=0\) in Lemma [lem:forward-hockey-stick-identity] gives the following closed form for ordinary sums of powers.
Proposition 10 (Ordinary sums of powers). For non-negative integers \(n\) and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+1}{k+1} - \binom{1-t}{k+1} \right] \Delta^{k} t^m. \end{align*}\]
The basis \(\binom{j-t+r}{k+r}\) in Lemma [lem:forward-hockey-stick-identity] is useful because it yields closed forms for sums of powers by varying the parameter \(r\). The next example illustrates the case \(r=1\).
Example 11. For integer \(0 \leq t \leq 3\), we have \[\begin{align*} \Sigma^{1}\,{n}^{3} &= 0\!\left[\tbinom{n+1}{1}-\tbinom{1}{1}\right] + 1\!\left[\tbinom{n+1}{2}-\tbinom{1}{2}\right] + 6\!\left[\tbinom{n+1}{3}-\tbinom{1}{3}\right] + 6\!\left[\tbinom{n+1}{4}-\tbinom{1}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 1\!\left[\tbinom{n}{2}-\tbinom{0}{2}\right] + 7\!\left[\tbinom{n}{3}-\tbinom{0}{3}\right] + 12\!\left[\tbinom{n}{4}-\tbinom{0}{4}\right] + 6\!\left[\tbinom{n}{5}-\tbinom{0}{5}\right], \\ % \Sigma^{1}\,{n}^{3} &= 8\!\left[\tbinom{n-1}{2}-\tbinom{-1}{2}\right] + 19\!\left[\tbinom{n-1}{3}-\tbinom{-1}{3}\right] + 18\!\left[\tbinom{n-1}{4}-\tbinom{-1}{4}\right] + 6\!\left[\tbinom{n-1}{5}-\tbinom{-1}{5}\right], \\ % \Sigma^{1}\,{n}^{3} &= 27\!\left[\tbinom{n-2}{2}-\tbinom{-2}{2}\right] + 37\!\left[\tbinom{n-2}{3}-\tbinom{-2}{3}\right] + 24\!\left[\tbinom{n-2}{4}-\tbinom{-2}{4}\right] + 6\!\left[\tbinom{n-2}{5}-\tbinom{-2}{5}\right]. \end{align*}\]
The preceding example contains binomial coefficients with negative upper indices. These coefficients are determined by the identity \(\binom{-n}{k} = (-1)^{k} \binom{k+n-1}{k}\). Setting \(t=0\) in Proposition [prop:ordinary-sums-of-powers] gives another well-known identity for sums of powers, discussed in (Graham et al. 1994, 190) and in (Pfaff 2007).
Corollary 12. For non-negative integers \(n\) and \(m\) \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \binom{n+1}{j+1} \Delta^{j} 0^m. \end{align*}\]
The following example illustrates the identity.
Example 13. For non-negative integer \(n\), we have \[\begin{align*} \Sigma^{1}\,{n}^{1} &= 1 \tbinom{n+1}{1}, \\ \Sigma^{1}\,{n}^{1} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2}, \\ \Sigma^{1}\,{n}^{2} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2} + 2 \tbinom{n+1}{3}, \\ \Sigma^{1}\,{n}^{3} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2} + 6 \tbinom{n+1}{3} + 6 \tbinom{n+1}{4}, \\ \Sigma^{1}\,{n}^{4} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2} + 14 \tbinom{n+1}{3} + 36 \tbinom{n+1}{4} + 24 \tbinom{n+1}{5}, \\ \Sigma^{1}\,{n}^{5} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2} + 30 \tbinom{n+1}{3} + 150 \tbinom{n+1}{4} + 240 \tbinom{n+1}{5} + 120 \tbinom{n+1}{6}. \end{align*}\]
The coefficients \(0,1,2,0,1,6,6,0,1,14,36,24,\dots\) are
given by the Stirling numbers of the second kind through \(a_k = k! \genfrac{\{}{\}}{0pt}{}{n}{k}\).
They form the sequence A131689 in the
OEIS (Sloane et al. 2003). Thus, Stirling numbers
of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\) arise
naturally from forward Newton interpolation for powers. Setting \(t=1\) in Proposition [prop:ordinary-sums-of-powers]
gives another well-known special case.
Corollary 14. For non-negative integers \(n\) and \(m\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \binom{n}{j+1} \Delta^{j} 1^m. \end{align*}\]
This identity is discussed, for example, in (Cereceda 2022). The following example illustrates it.
Example 15. For non-negative integer \(n\), we have \[\begin{align*} \Sigma^{1}\,{n}^{0} &= 1 \tbinom{n}{1}, \\ \Sigma^{1}\,{n}^{1} &= 1 \tbinom{n}{1} + 1 \tbinom{n}{2}, \\ \Sigma^{1}\,{n}^{2} &= 1 \tbinom{n}{1} + 3 \tbinom{n}{2} +2 \tbinom{n}{3}, \\ \Sigma^{1}\,{n}^{3} &= 1 \tbinom{n}{1} + 7 \tbinom{n}{2} +12 \tbinom{n}{3} + 6 \tbinom{n}{4}, \\ \Sigma^{1}\,{n}^{4} &= 1 \tbinom{n}{1} +15 \tbinom{n}{2} +50 \tbinom{n}{3} +60 \tbinom{n}{4} + 24 \tbinom{n}{5}, \\ \Sigma^{1}\,{n}^{5} &= 1 \tbinom{n}{1} +31 \tbinom{n}{2} +180 \tbinom{n}{3} +390 \tbinom{n}{4} + 360 \tbinom{n}{5} + 120 \tbinom{n}{6}. \end{align*}\]
The displayed coefficients belong to OEIS sequence A028246 (Sloane et al. 2003). The work in (Cereceda 2022)
gives formulas for sums of powers in terms of generalized Stirling
numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{k}{j}_{r}\).
Specifically, it gives the following result.
Proposition 16 (Cereceda (2022)). For non-negative integers \(n\) and \(k\), \[\begin{align} \label{eq:cereceda-sums-1} \Sigma^{1}\,{n}^{k} &= \sum_{j=0}^{k} j! \left[ \binom{n+1-r}{j+1} + (-1)^j \binom{r+j-1}{j+1} \right] \genfrac{\{}{\}}{0pt}{}{k}{j}_{r}. \end{align}\] The same work also gives \[\begin{align} \label{eq:cereceda-sums-2} \Sigma^{1}\,{n}^{k} &= \sum_{j=0}^{k} j! \left[ \binom{n+1+r}{j+1} + \binom{r+1}{j+1} \right] \genfrac{\{}{\}}{0pt}{}{k}{j}_{-r}. \end{align}\]
Equation [eq:cereceda-sums-1] is a special case of Proposition [prop:ordinary-sums-of-powers], obtained by setting \(t=r\) and applying the upper-binomial negation identity in Lemma [lem:upper-binomial-negation] to \(\binom{1-t}{k+1}\). The forward finite differences of powers can also be expressed in terms of generalized Stirling numbers of the second kind: \[\begin{align} \label{eq:gen-stirling-finit-difference} \Delta^{k} t^m = k! \genfrac{\{}{\}}{0pt}{}{m}{k}_{t}. \end{align}\] This identity shows that generalized Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}_t\) arise naturally from forward Newton interpolation for powers evaluated at an arbitrary integer \(t\). Equation [eq:cereceda-sums-2] is another special case of Proposition [prop:ordinary-sums-of-powers], obtained by setting \(t=-r\) and using Equation [eq:gen-stirling-finit-difference]. Setting \(t=4\) in Proposition [prop:ordinary-sums-of-powers] gives the following less familiar formulas for sums of powers.
Example 17. For non-negative integer \(n\), we have \[\begin{align*} \Sigma^{1}\,{n}^{0} &= 1 \left( \tbinom{n-3}{1} + \tbinom{3}{1} \right), \\ \Sigma^{1}\,{n}^{1} &= 4 \left( \tbinom{n-3}{1} + \tbinom{3}{1} \right) + 1 \left( \tbinom{n-3}{2} - \tbinom{4}{2} \right), \\ \Sigma^{1}\,{n}^{2} &= 16 \left( \tbinom{n-3}{1} + \tbinom{3}{1} \right) + 9 \left( \tbinom{n-3}{2} - \tbinom{4}{2} \right) + 2 \left( \tbinom{n-2}{3} + \tbinom{5}{3} \right), \\ \Sigma^{1}\,{n}^{3} &= 64 \left( \tbinom{n-3}{1} + \tbinom{3}{1} \right) + 61 \left( \tbinom{n-3}{2} - \tbinom{4}{2} \right) + 30 \left( \tbinom{n-3}{3} + \tbinom{5}{3} \right) + 6 \left( \tbinom{n-3}{4} - \tbinom{6}{4} \right). \end{align*}\]
The coefficients \(1,4,1,16,9,\dots\) form the sequence A391633 in the
OEIS (Sloane et al. 2003). We now consider double
sums of powers. Setting \(r=1\) in the
hockey-stick identity from Lemma [lem:forward-hockey-stick-identity]
and including the correction terms \(\Sigma^{r}\,{n}^{0}\) gives the following
formula.
Proposition 18 (Double sums of powers). For non-negative integers \(n\) and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+2}{k+2} - \binom{1-t}{k+1} \Sigma^{1}\,{n}^{0} - \binom{2-t}{k+2} \Sigma^{0}\,{n}^{0} \right] \Delta^{k} t^m. \end{align*}\]
The zero-power sums satisfy \(\Sigma^{1}\,{n}^{0}=n\) and \(\Sigma^{0}\,{n}^{0}=1\). Applying the upper-binomial negation identity from Lemma [lem:upper-binomial-negation] gives the following equivalent formula.
Proposition 19 (Double sums of powers negated). For non-negative integers \(n\) and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+2}{k+2} + (-1)^k \binom{k+t-1}{k+1} n + (-1)^{k+1} \binom{k+t-1}{k+2} \right] \Delta^{j} t^m. \end{align*}\]
Setting \(t=5\) in Proposition [prop:double-sums-of-powers-negated] gives the following example.
Example 20. For non-negative integer \(n\), we have \[\begin{align*} \Sigma^{2}\,{n}^{0} &= 1 \left( \tbinom{n-3}{2} + \tbinom{4}{1} n - \tbinom{4}{2} \right), \\ \Sigma^{2}\,{n}^{1} &= 5 \left( \tbinom{n-3}{2} + \tbinom{4}{1} n - \tbinom{4}{2} \right) + 1 \left( \tbinom{n-3}{3} - \tbinom{5}{2} n + \tbinom{5}{3} \right), \\ \Sigma^{2}\,{n}^{2} &= 25 \left( \tbinom{n-3}{2} + \tbinom{4}{1} n - \tbinom{4}{2} \right) + 11 \left( \tbinom{n-3}{3} - \tbinom{5}{2} n + \tbinom{5}{3} \right) + 2 \left( \tbinom{n-3}{4} + \tbinom{6}{3} n - \tbinom{6}{4} \right), \\ \Sigma^{2}\,{n}^{3} &= 125 \left( \tbinom{n-3}{2} + \tbinom{4}{1} n - \tbinom{4}{2} \right) + 91 \left( \tbinom{n-3}{3} - \tbinom{5}{2} n + \tbinom{5}{3} \right) + 36 \left( \tbinom{n-3}{4} + \tbinom{6}{3} n - \tbinom{6}{4} \right) \\ &+ 6 \left( \tbinom{n-3}{5} - \tbinom{7}{3} n + \tbinom{7}{4} \right). \end{align*}\]
The coefficients \(1,5,1,25,11,2,\dots\) form the sequence A391635 in the
OEIS (Sloane et al. 2003). Repeating the
procedure used for \(\Sigma^{1}\,{n}^{m}\) and \(\Sigma^{2}\,{n}^{m}\) gives a general
formula for \(r\)-fold sums of
powers.
Theorem 21 (Multifold sums of powers). For non-negative integers \(r\), \(n\), and \(m\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \Delta^{k} t^{m}. \end{align*}\]
Using Lemma [lem:multifold-sum-of-zero-powers], we obtain the following pure binomial form.
Proposition 22 (Multifold binomial sums of powers). For non-negative integers \(r\), \(n\), and \(m\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \binom{s+n-1}{s} \right] \Delta^{k} t^{m}. \end{align*}\]
Explicitly, \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \bigg[ \tbinom{n-t+r}{k+r} - \tbinom{r-t}{k+r} \tbinom{n-1}{0} - \tbinom{r-1-t}{k+r-1} \tbinom{n}{1} - \cdots - \tbinom{2-t}{k+2} \tbinom{r+n-3}{r-2} - \tbinom{1-t}{k+1} \tbinom{r+n-2}{r-1} \bigg] \Delta^{k} t^{m}. \end{align*}\] The following example illustrates these formulas.
Example 23. For non-negative integers \(r\), \(n\), and \(m\) we have \[\begin{align*} \Sigma^{r}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+r-0}{k+r} - \mathop{\textstyle\sum}_{s=0}^{r-1} \tbinom{r-s}{k+r-s} \tbinom{s+n-1}{s} \right] \Delta^k 0^m, \\ \Sigma^{r}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+r-1}{k+r} - \mathop{\textstyle\sum}_{s=0}^{r-1} \tbinom{r-s-1}{k+r-s} \tbinom{s+n-1}{s} \right] \Delta^k 1^m, \\ \Sigma^{r}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+r-2}{k+r} - \mathop{\textstyle\sum}_{s=0}^{r-1} \tbinom{r-s-2}{k+r-s} \tbinom{s+n-1}{s} \right] \Delta^k 2^m, \\ \Sigma^{r}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+r-3}{k+r} - \mathop{\textstyle\sum}_{s=0}^{r-1} \tbinom{r-s-3}{k+r-s} \tbinom{s+n-1}{s} \right] \Delta^k 3^m. \end{align*}\]
These formulas are polynomials in \(n\) with integer coefficients given by forward finite differences of powers evaluated at an arbitrary integer \(t\). The following example lists the cases \(0\leq t\leq4\).
Example 24. For \(r=1\) and \(m=3\), Proposition 22 yields \[\begin{align*} t=0:\quad \Sigma^{1}\,{n}^{3} &= n\cdot0 +\tfrac{1}{2}(n+n^2)\cdot1 +\tfrac{1}{6}(-n+n^3)\cdot6 +\tfrac{1}{24}(2n-n^2-2n^3+n^4)\cdot6, \\ t=1:\quad \Sigma^{1}\,{n}^{3} &= n\cdot1 +\tfrac{1}{2}(-n+n^2)\cdot7 +\tfrac{1}{6}(2n-3n^2+n^3)\cdot12 \\ &+\tfrac{1}{24}(-6n+11n^2-6n^3+n^4)\cdot6, \\ t=2:\quad \Sigma^{1}\,{n}^{3} &= n\cdot8 +\tfrac{1}{2}(-3n+n^2)\cdot19 +\tfrac{1}{6}(11n-6n^2+n^3)\cdot18 \\ &+\tfrac{1}{24}(-50n+35n^2-10n^3+n^4)\cdot6, \\ t=3:\quad \Sigma^{1}\,{n}^{3} &= n\cdot27 +\tfrac{1}{2}(-5n+n^2)\cdot37 +\tfrac{1}{6}(26n-9n^2+n^3)\cdot24 \\ &+\tfrac{1}{24}(-154n+71n^2-14n^3+n^4)\cdot6, \\ t=4:\quad \Sigma^{1}\,{n}^{3} &= n\cdot64 +\tfrac{1}{2}(-7n+n^2)\cdot61 +\tfrac{1}{6}(47n-12n^2+n^3)\cdot30 \\ &+\tfrac{1}{24}(-342n+119n^2-18n^3+n^4)\cdot6. \end{align*}\]
The coefficients have the following forms.
For \(t=0\), the coefficients
\(0,1,6,6\) belong to the OEIS sequence
A131689.
For \(t=1\), the coefficients
\(1,7,12,6\) belong to the OEIS
sequence A028246.
For \(t=2\), the coefficients
\(8,19,18,6\) belong to the OEIS
sequence A038719.
For \(t=3\), the coefficients
\(27,37,24,6\) belong to the OEIS
sequence A391552.
For \(t=4\), the coefficients
\(64,61,30,6\) belong to the OEIS
sequence A391633.
We first express forward finite differences in terms of Stirling numbers.
Lemma 25 (Stirling finite differences). For non-negative integers \(k\) and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Delta^{k} t^{m} = \sum_{j=0}^{m} \genfrac{\{}{\}}{0pt}{}{m}{k+j} \binom{t}{j} (k+j)!. \end{align*}\]
Proof. Applying the well-known identity \(t^{m} = \mathop{\textstyle\sum}_{j=0}^{m} \genfrac{\{}{\}}{0pt}{}{m}{j} \tbinom{t}{j} j!\) to the forward difference gives the stated formula. ◻
Substituting this expression into Theorem [thm:multifold-sums-of-powers] gives the following formula.
Proposition 26 (Multifold Stirling sums). For non-negative integers \(r\), \(n\), and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \sum_{j=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \genfrac{\{}{\}}{0pt}{}{m}{k+j} \binom{t}{j} (k+j)!. \end{align*}\]
Applying Lemma [lem:multifold-sum-of-zero-powers] gives the following pure binomial form.
Proposition 27 (Multifold Stirling-Binomial sums). For non-negative integers \(r\), \(n\), and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \sum_{j=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \binom{s+n-1}{s} \right] \genfrac{\{}{\}}{0pt}{}{m}{k+j} \binom{t}{j} (k+j)!. \end{align*}\]
We begin with Worpitzky’s identity.
Lemma 28 (Worpitzky Identity). For non-negative integers \(t\) and \(m\), \[\begin{align*} t^{m} = \sum_{k=0}^{m} \binom{t+k}{m} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}, \end{align*}\] where \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\) are Eulerian numbers.
Proof. The identity is given by J. Worpitzky in (Worpitzky 1883). ◻
The following lemma expresses finite differences of powers in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{m}{s}\).
Lemma 29 (Eulerian finite differences). For non-negative integers \(k\) and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Delta^{k} t^{m} = \sum_{j=0}^{m} \binom{t+j}{m-k} \genfrac{\langle}{\rangle}{0pt}{}{m}{j}. \end{align*}\]
Proof. This follows from the binomial recurrence \(\tbinom{n+1}{k} = \tbinom{n}{k} + \tbinom{n}{k-1}\) and Worpitzky’s identity in Lemma [lem:worpitzky-identity]. ◻
Substituting this expression into Theorem [thm:multifold-sums-of-powers] gives the following formula.
Proposition 30 (Multifold Eulerian sums). For non-negative integers \(r\), \(n\), and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \sum_{j=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \binom{t+j}{m-k} \genfrac{\langle}{\rangle}{0pt}{}{m}{j}. \end{align*}\]
Applying Lemma [lem:multifold-sum-of-zero-powers] gives the following pure binomial form.
Proposition 31 (Multifold Eulerian-Binomial sums). For non-negative integers \(r\), \(n\), and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \sum_{j=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \binom{s+n-1}{s} \right] \binom{t+j}{m-k} \genfrac{\langle}{\rangle}{0pt}{}{m}{j}. \end{align*}\]
We first relate forward and backward finite differences.
Lemma 32 (Forward-Backward relation). For non-negative integers \(k\) and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Delta^{k} t^{m} = \nabla^{k} (t+k)^{m}, \end{align*}\] where \[\begin{align*} \nabla^{k} t^{m} = \mathop{\textstyle\sum}_{j=0}^{k} (-1)^j \tbinom{k}{j} (t-j)^m. \end{align*}\]
Applying Lemma [lem:forward-via-backward-differences] to Theorem [thm:multifold-sums-of-powers] gives the following formula.
Proposition 33 (Multifold Backward sums). For non-negative integers \(r\), \(n\), and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \nabla^{k} (t+k)^{m}. \end{align*}\]
Applying Lemma [lem:multifold-sum-of-zero-powers] gives the following pure binomial form.
Proposition 34 (Multifold Backward-Binomial sums). For non-negative integers \(r\), \(n\), and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \binom{s+n-1}{s} \right] \nabla^{k} (t+k)^{m}. \end{align*}\]
We first relate forward and central finite differences.
Lemma 35 (Forward-central relation). For non-negative integers \(k\) and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Delta^{k} t^{m} = \delta^{k} \left( t+ \frac{k}{2} \right)^{m}, \end{align*}\] where \[\begin{align*} \delta^{k} t^m = \mathop{\textstyle\sum}_{j=0}^{k} (-1)^j \tbinom{k}{j} \left( t + \tfrac{k}{2} - j \right)^{m}. \end{align*}\]
Applying Lemma [lem:forward-via-central-differences] to Theorem [thm:multifold-sums-of-powers] gives the following formula.
Proposition 36 (Multifold Central sums). For non-negative integers \(r\), \(n\), and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \delta^{k} \left( t+ \frac{k}{2} \right)^{m}. \end{align*}\]
Applying Lemma [lem:multifold-sum-of-zero-powers] gives the following pure binomial form.
Proposition 37 (Multifold Central-Binomial sums). For non-negative integers \(r\), \(n\), and \(m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+r}{k+r} - \sum_{s=0}^{r-1} \binom{r-s-t}{k+r-s} \binom{s+n-1}{s} \right] \delta^{k} \left( t+ \frac{k}{2} \right)^{m}. \end{align*}\]
In this manuscript, we derive closed formulas for multifold sums of powers of integers by combining the forward Newton interpolation formula with hockey-stick identities for binomial coefficients. We further obtain representations of multifold sums of powers in terms of Stirling numbers of the second kind and Eulerian numbers. Finally, we provide Wolfram Mathematica programs for the efficient verification of the derived identities.
The author thanks Markus Scheuer for his assistance in identifying
literature on central factorial numbers and Newton’s interpolation
formula. See the relevant discussion at math.stackexchange.com/a/3665722/463487.
Use the Mathematica programs in the project repository to validate
the results. Table 1 lists the programs and
the results they validate. The repository is available at GitHub.
| Mathematica Function | Validates or Prints |
|---|---|
ValidateMultifoldSumsOfPowers.txt |
Validates Theorem [thm:multifold-sums-of-powers] |
ValidateMultifoldBinomialSumsOfPowers.txt |
Validates Proposition [prop:multifold-binomial-sums-of-powers] |
ValidateMultifoldStirlingSums.txt |
Validates Proposition [prop:multifold-stirling-sums] |
ValidateMultifoldStirlingBinomialSums.txt |
Validates Proposition [prop:multifold-stirling-binomial-sums] |
ValidateMultifoldEulerianSums.txt |
Validates Proposition [prop:multifold-eulerian-sums] |
ValidateMultifoldEulerianBinomialSums.txt |
Validates Proposition [prop:multifold-eulerian-binomial-sums] |
ValidateMultifoldBackwardSums.txt |
Validates Proposition [prop:multifold-backward-sums] |
ValidateMultifoldBackwardBinomialSums.txt |
Validates Proposition [prop:multifold-backward-binomial-sums] |
ValidateMultifoldCentralSums.txt |
Validates Proposition [prop:multifold-central-sums] |
ValidateMultifoldCentralBinomialSums.txt |
Validates Proposition [prop:multifold-central-binomial-sums] |
Metadata
Initial release date: December 24, 2025.
Current release date: 2026-11-07.
Version:
2.1.0+main.d104d02
MSC2010: 05A19, 05A10, 41A15, 11B83
Keywords: Sums of powers, Newton’s interpolation formula, Finite differences, Binomial coefficients, Newton’s series, Faulhaber’s formula, Bernoulli numbers, Bernoulli polynomials, Interpolation, Combinatorics, Central factorial numbers, Stirling numbers, Eulerian numbers, Worpitzky identity, OEIS
License: This work is licensed under a CC BY 4.0 License.
Web Version: kolosovpetro.github.io/sums-of-powers-newtons-formula
Sources: github.com/kolosovpetro/NewtonsFormulaAndSumsOfPowers
ORCID: 0000-0002-6544-8880
Email: kolosovp94@gmail.com