2026-06-28
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.
In this section, allow us to define a few lemmas, definitions, and conventions that serve as foundation for main results of this manuscript. For multifold sums of powers, we use the notation provided by Donald Knuth in (Knuth, Donald E. 1993), because it is simple and beautiful
Definition 1 (Multifold sums of powers). For non-negative integers \(r,n,m\) \[\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 utilize the following notation for rising factorials
Definition 2 (Rising factorials). For integers \(n,k\) \[\begin{align*} n^{\left(k\right)} = \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*}\]
We encourage the audience to read J. F. Steffensen’s work on the definition of generalized factorials (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}\). Then, for all \(n \in \mathbb{Z}\), \[\begin{align*} f(n) = \sum_{k=0}^{\infty} \frac{(n-t)^{\left(k\right)}}{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. Originally revealed by Sir Isaac Newton in (Newton, Isaac and Chittenden, N.W. 1850). Expressed in modern mathematical notation by J. F. Steffensen in (Steffensen, Johan Frederik 1927, sec. 2, eq. (19)). By using identity \(\frac{(n-t)^{\left(k\right)}}{k!} = \binom{n-t}{k}\), we get RHS. ◻
Lemma 4 (Forward Newton’s formula for powers). For non-negative integers \(n,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. Special case of Lemma [lem:forward-newtons-formula] for powers. ◻
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, \(\sum_{k=a}^{b} \binom{k}{j} = \binom{a}{j} + \binom{a+1}{j} + \cdots + \binom{b}{j} = \left( \sum_{k=0}^{b} \binom{k}{j} \right) - \left( \sum_{k=0}^{a-1} \binom{k}{j} \right)\). By hockey-stick identity \(\sum_{k=0}^{n} \binom{k}{j} = \binom{n+1}{j+1}\) yields, \[\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 completes the proof. ◻
Lemma 6 (Forward hockey-stick identity). For integer \(n\geq1\), and arbitrary integers \(t,k,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. By setting \(a=1-t+r\), and \(b=n-t+1\) into Lemma [lem:generalized-hockey-stick-identity]. ◻
Lemma 7 (Multifold sums of zero powers). For non-negative integers \(r,n\) \[\begin{align*} \Sigma^{r}\,{n}^{0} = \binom{r+n-1}{r}. \end{align*}\]
Proof.
Let \(r=0\), then we have \(\Sigma^{0}\,{n}^{0} = 1\), by definition [def:multifold-sums-of-powers-recurrence].
Let \(r=1\), then we have \(\Sigma^{1}\,{n}^{0} = \sum_{k=1}^{n} 1 = \binom{n}{1}\).
Let \(r=2\), then we have \(\Sigma^{2}\,{n}^{0} = \sum_{k=1}^{n} \binom{k}{1} = \binom{n+1}{2}\).
Let \(r=3\), then we have \(\Sigma^{3}\,{n}^{0} = \sum_{k=1}^{n} \binom{k+1}{2} = \binom{n+2}{3}\).
Similarly, for arbitrary integer \(r\), by hockey-stick identity \(\sum_{k=1}^{n} \binom{k}{r} = \binom{n+1}{r+1}\), yields \(\Sigma^{r}\,{n}^{0} = \sum_{k=1}^{n} \Sigma^{r-1}\,{k}^{0} = \sum_{k=1}^{n} \binom{k+r-2}{r-1} = \binom{r+n-1}{r}\).
This completes the proof. ◻
Lemma 8 (Upper Binomial negation). For integers \(n,k\) \[\begin{align*} \binom{-n}{k} = (-1)^{k} \binom{k+n-1}{k} \end{align*}\]
Proof. See (Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren 1994, 164, eq. (5.14)). ◻
Convention 9. For all \(x\) \[\begin{align*} x^0 = 1. \end{align*}\]
Donald Knuth give extensive discussion on the convention \(x^0=1\) for all \(x\), including zero, in Concrete Mathematics (Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren 1994, 162), and in (Knuth 1992).
In this manuscript, we derive formulas for sums of powers by combining forward Newton’s interpolation formula for powers [lem:forward-newtons-formula-for-powers] with hockey-stick identity [lem:forward-hockey-stick-identity]. We implement the algorithm for finding closed forms of sums of powers of integers, proposed in (Kolosov 2026, Alg. (11.2)). More precisely, the main idea is to determine binomial basis of Newton’s formula, in terms of variants of difference operators, for example \[\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{(x-a)^{\left(k\right)}}{k!} \Delta^k f(a) = \sum_{k=0}^{\infty} \binom{x-a}{k} \Delta^k f(a), \\ f(x) &= \sum_{k=0}^{\infty} \frac{\left(x-a\right)_{k}}{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*}\] We may observe that each variation of Newton’s formula above has its 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*}\] This allows us to successfully combine Newton’s formula with hockey-stick type identity, to find closed forms for sums of powers of integers. In this manuscript, we focus on closed forms of powers sums, by utilizing forward Newton’s formula, and hockey-stick identity [lem:forward-hockey-stick-identity].
We start our discussion from Lemma [lem:forward-newtons-formula-for-powers], which yields forward Newton’s interpolation formula for powers. For example, \[\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*}\]
Thus, the transition to formula for sums of powers is quite straightforward, \[\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*}\] Therefore, by setting \(r=0\) into Lemma [lem:forward-hockey-stick-identity] yields closed form of ordinary sums of powers
Proposition 10 (Ordinary sums of powers). For non-negative integers \(n,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*}\]
We may see that the basis \(\binom{j-t+r}{k+r}\) for repeatedly applied Lemma [lem:forward-hockey-stick-identity] was indeed chosen correctly, because we derived closed form for sums of powers with ease, simply setting parameter for \(r\). For example,
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*}\]
From example above, we may observe binomial coefficients of negative upper index, which may looking unfamiliar. However, there is no reason to be afraid of, because negative upper index binomial coefficients are completely deterministic, because \(\binom{-n}{k} = (-1)^{k} \binom{k+n-1}{k}\). By setting \(t=0\) into Proposition [prop:ordinary-sums-of-powers] yields one more well-known identity for sums of powers, mentioned in (Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren 1994, 190), and in (Pfaff 2007)
Corollary 12. For non-negative integers \(n,m\) \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \binom{n+1}{j+1} \Delta^{j} 0^m. \end{align*}\]
For example,
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*}\]
From the example above, we observe the coefficients \(0,1,2,0, 1, 6, 6, 0, 1, 14, 36, 24,
\dots\), are defined by Stirling numbers of the second kind \(a_k = k! \genfrac{\{}{\}}{0pt}{}{n}{k}\),
which is the sequence A131689 in the
OEIS (Sloane, Neil
J.A. and others 2003). This leads us to the notion, that Stirling
numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\) recover
naturally from forward Newton’s interpolation formula for powers. By
setting \(t=1\) into Proposition [prop:ordinary-sums-of-powers],
we get another well-known special case
Corollary 14. For non-negative integers \(n,m\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \binom{n}{j+1} \Delta^{j} 1^m, \end{align*}\]
mentioned, for instance, in (Cereceda, José L. 2022). For example,
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 coefficients \(1,1,1,1,3,2,1,7,12,6,1,15, \dots\) is the
sequence A028246 in
the OEIS (Sloane,
Neil J.A. and others 2003). It is interesting to note that the
work (Cereceda,
José L. 2022) provide formulas for sums of powers in terms of
generalized Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{k}{j}_{r}\), that
is
Proposition 16 (Cereceda (2022)). For non-negative integers \(n,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}\] And \[\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}\]
Formula [eq:cereceda-sums-1] is a special case of Proposition [prop:ordinary-sums-of-powers] with setting \(t \rightarrow r\), and upper negated binomial coefficient \(\binom{1-t}{k+1}\), by using upper negation formula from Lemma [lem:upper-binomial-negation]. We may observe that forward finite difference of powers \(\Delta^{k} t^m\) can be expressed in terms of generalized Stirling numbers of the second kind, that is \[\begin{align} \label{eq:gen-stirling-finit-difference} \Delta^{k} t^m = k! \genfrac{\{}{\}}{0pt}{}{m}{k}_{t}. \end{align}\] This leads us to the observation, that generalized Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}_t\) recover naturally from forward Newton’s interpolation formula for powers, evaluated in arbitrary integer \(t\). Now, reviewing Formula [eq:cereceda-sums-2], we notice that it is a special case of Proposition [prop:ordinary-sums-of-powers] with setting \(t \rightarrow -r\), and by using Equation [eq:gen-stirling-finit-difference]. For example, by setting \(t=4\) into Proposition [prop:ordinary-sums-of-powers] yields rather unusual 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\) is the sequence A391633 in the
OEIS (Sloane, Neil
J.A. and others 2003). As we have all required identities in our
disposal, consider the case of double sums of powers. Surely, we derive
its formula with ease, and gracefully, by setting \(r=1\) into hockey-stick identity from
Lemma [lem:forward-hockey-stick-identity],
with additional correction terms \(\Sigma^{r}\,{n}^{0}\). Therefore,
Proposition 18 (Double sums of powers). For non-negative integers \(n,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*}\]
Note that \(\Sigma^{1}\,{n}^{0}=n\), and \(\Sigma^{0}\,{n}^{0}=1\). By applying upper binomial negation formula from Lemma [lem:upper-binomial-negation] yields
Proposition 19 (Double sums of powers negated). For non-negative integers \(n,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*}\]
For example, by setting \(t=5\) into Proposition [prop:double-sums-of-powers-negated] yields
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\) is the sequence A391635 in the
OEIS (Sloane, Neil
J.A. and others 2003). Therefore, generalized formula for \(r\)-fold sums of powers is straightforward,
repeating the same procedure as we have done for \(\Sigma^{1}\,{n}^{m}\), and \(\Sigma^{2}\,{n}^{m}\)
Theorem 21 (Multifold sums of powers). For non-negative integers \(r,n,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*}\]
Which is quite remarkable in its pure binomial form, by using Lemma [lem:multifold-sum-of-zero-powers]
Proposition 22 (Multifold binomial sums of powers). For non-negative integers \(r,n,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*}\] For example,
Example 23. For non-negative integers \(r,n,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 which are forward finite differences of powers, evaluated at arbitrary integer \(t\). For example, for integer \(0 \leq t \leq 4\), we have
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*}\]
Where the coefficients
For \(t=0\) are \(0, 1, 6, 6\) belong to the sequence A131689 in the
OEIS.
For \(t=1\) are \(1, 7, 12, 6\) belong to the sequence A028246 in the
OEIS.
For \(t=2\) are \(8, 19, 18, 6\) belong to the sequence A038719 in the
OEIS.
For \(t=3\) are \(27, 37, 24, 6\) belong to the sequence A391552 in the
OEIS.
For \(t=4\) are \(64, 61, 30, 6\) belong to the sequence A391633 in the
OEIS.
We have
Lemma 25 (Stirling finite differences). For non-negative integers \(k,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. By well-known identity \(t^{m} = \sum_{j=0}^{m} \genfrac{\{}{\}}{0pt}{}{m}{j} \binom{t}{j} j!\) ◻
Thus, from Theorem [thm:multifold-sums-of-powers] follows
Proposition 26 (Multifold Stirling sums). For non-negative integers \(r,n,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*}\]
By Lemma [lem:multifold-sum-of-zero-powers], the pure binomial form follows
Proposition 27 (Multifold Stirling-Binomial sums). For non-negative integers \(r,n,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 have
Lemma 28 (Worpitzky identity). For non-negative integers \(t,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. See the (1883) work of J. Worpitzky (Worpitzky 1883). ◻
Thus, we obtain formula for finite differences of powers, in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{m}{s}\)
Lemma 29 (Eulerian finite differences). For non-negative integers \(t,k\), 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. By binomial recurrence \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\), and by Worpitzky identity [lem:worpitzky-identity]. ◻
Thus, from Theorem [thm:multifold-sums-of-powers] follows
Proposition 30 (Multifold Eulerian sums). For non-negative integers \(r,n,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*}\]
By Lemma [lem:multifold-sum-of-zero-powers], the pure binomial form follows
Proposition 31 (Multifold Eulerian-Binomial sums). For non-negative integers \(r,n,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 have
Lemma 32 (Forward-Backward relation). For non-negative integers \(k,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*}\]
Thus, from Theorem [thm:multifold-sums-of-powers] follows
Proposition 33 (Multifold Backward sums). For non-negative integers \(r,n,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*}\]
By Lemma [lem:multifold-sum-of-zero-powers], the pure binomial form follows
Proposition 34 (Multifold Backward-Binomial sums). For non-negative integers \(r,n,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 have
Lemma 35 (Forward-Central relation). For non-negative integers \(k,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*}\]
Thus, from Theorem [thm:multifold-sums-of-powers] follows
Proposition 36 (Multifold Central sums). For non-negative integers \(r,n,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*}\]
By Lemma [lem:multifold-sum-of-zero-powers], the pure binomial form follows
Proposition 37 (Multifold Central-Binomial sums). For non-negative integers \(r,n,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 is grateful to Markus Scheuer for his valuable assistance
in identifying the literature related to central factorial numbers and
Newton’s interpolation formula. Visit math.stackexchange.com/a/3665722/463487.
Use this GitHub
repository to validate the results using Mathematica programs.
| Mathematica Function | Validates / Prints |
|---|---|
ValidateMultifoldSumsOfPowers.txt |
Validates Thm. [thm:multifold-sums-of-powers] |
ValidateMultifoldBinomialSumsOfPowers.txt |
Validates Prop. [prop:multifold-binomial-sums-of-powers] |
ValidateMultifoldStirlingSums.txt |
Validates Prop. [prop:multifold-stirling-sums] |
ValidateMultifoldStirlingBinomialSums.txt |
Validates Prop. [prop:multifold-stirling-binomial-sums] |
ValidateMultifoldEulerianSums.txt |
Validates Prop. [prop:multifold-eulerian-sums] |
ValidateMultifoldEulerianBinomialSums.txt |
Validates Prop. [prop:multifold-eulerian-binomial-sums] |
ValidateMultifoldBackwardSums.txt |
Validates Prop. [prop:multifold-backward-sums] |
ValidateMultifoldBackwardBinomialSums.txt |
Validates Prop. [prop:multifold-backward-binomial-sums] |
ValidateMultifoldCentralSums.txt |
Validates Prop. [prop:multifold-central-sums] |
ValidateMultifoldCentralBinomialSums.txt |
Validates Prop. [prop:multifold-central-binomial-sums] |
Metadata
Initial release date: December 24, 2025.
Current release date: 2026-06-28.
Version:
2.0.1+main.4c3ba8a
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