2026-11-12
In this manuscript, we derive closed formulas for multifold sums of powers of integers by combining the backward 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, we introduce several lemmas, definitions, and conventions that serve as the foundation for the main results of this manuscript. For multifold sums of powers, we use the notation provided by Donald Knuth in (Knuth, Donald E. 1993), which is concise and useful.
Definition 1 (Multifold Sums of Powers). For non-negative integers \(r\), \(n\), and \(m\), the multifold sums are defined recursively 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 rising factorials.
Definition 2 (Rising Factorials). For integers \(n\) and \(k\), define the rising factorial by \[\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*}\]
For further discussion of generalized factorials, see J. F. Steffensen (Steffensen 1933).
Lemma 3 (Backward 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!} \nabla^{k} f(t) = \sum_{k=0}^{\infty} \binom{n-t+k-1}{k} \nabla^{k} f(t), \end{align*}\] Here, \(\nabla^{k} f(t)\) denotes the \(k\)-th backward difference of \(f\) evaluated at \(t\) \[\begin{align*} \nabla^{k} t^{m} = \mathop{\textstyle\sum}_{j=0}^{k} (-1)^j \tbinom{k}{j} (t-j)^m. \end{align*}\]
Proof. Sir Isaac Newton originally presented this formula in (Newton, Isaac and Chittenden, N.W. 1850). J. F. Steffensen expressed it in modern mathematical notation in (Steffensen, Johan Frederik 1927, sec. 2, Equation (19)). The identity \(\frac{(n-t)^{\left(k\right)}}{k!} = \binom{n-t+k-1}{k}\) gives the binomial form. ◻
Lemma 4 (Backward Newton’s formula for powers). For non-negative integers \(n\) and \(m\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} n^m = \sum_{k=0}^{m} \binom{n-t+k-1}{k} \nabla^{k} t^m. \end{align*}\]
Proof. This is the special case of Lemma [lem:backward-newtons-formula] for powers. ◻
Lemma 5 (Generalized Hockey-Stick Identity). For arbitrary integers \(a\), \(b\), and \(j\), the following identity holds \[\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)\). The hockey-stick identity \(\sum_{k=0}^{n} \binom{k}{j} = \binom{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 completes the proof. ◻
Lemma 6 (Backward Hockey-Stick Identity). For an integer \(n\geq1\) and arbitrary integers \(t\), \(k\), and \(r\), the following identity holds \[\begin{align*} \sum_{j=1}^{n} \binom{j-t+k-1+r}{k+r} = \binom{n-t+k+r}{k+r+1} - \binom{k-t+r}{k+r+1}. \end{align*}\]
Proof. Setting \(a=k-t+r\) and \(b=n-t+k-1+r\) in Lemma [lem:generalized-hockey-stick-identity] gives the result. ◻
Lemma 7 (Multifold Sums of Zero Powers). For non-negative integers \(r\) and \(n\), the following identity holds \[\begin{align*} \Sigma^{r}\,{n}^{0} = \binom{r+n-1}{r}. \end{align*}\]
Proof.
When \(r=0\), Definition 1 gives \(\Sigma^{0}\,{n}^{0} = 1\).
When \(r=1\), we have \(\Sigma^{1}\,{n}^{0} = \sum_{k=1}^{n} 1 = \binom{n}{1}\).
When \(r=2\), we have \(\Sigma^{2}\,{n}^{0} = \sum_{k=1}^{n} \binom{k}{1} = \binom{n+1}{2}\).
When \(r=3\), we have \(\Sigma^{3}\,{n}^{0} = \sum_{k=1}^{n} \binom{k+1}{2} = \binom{n+2}{3}\).
For arbitrary non-negative integer \(r\), iterating the definition and applying the hockey-stick identity gives \[\begin{align*} \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}. \end{align*}\]
This completes the proof. ◻
Lemma 8 (Upper Binomial Negation). For integers \(n\) and \(k\), the following identity holds \[\begin{align*} \binom{n}{k} &= (-1)^{k} \binom{k-n-1}{k}, \\ \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, Equation (5.14)). ◻
Convention 9. For every \(x\), we use the convention \[\begin{align*} x^0 = 1. \end{align*}\]
Donald Knuth gives an extensive discussion of 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 backward Newton’s interpolation formula for powers in Lemma [lem:backward-newtons-formula-for-powers] with the hockey-stick identity in Lemma [lem:backward-hockey-stick-identity]. We apply 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 identify the binomial basis of Newton’s formula for several difference operators. The corresponding variants are \[\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 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 bases allow us to combine Newton’s formula with hockey-stick-type identities to find closed forms for sums of powers of integers. Accordingly, the main results use backward Newton’s formula and the hockey-stick identity in Lemma [lem:backward-hockey-stick-identity].
We begin with Lemma [lem:backward-newtons-formula-for-powers], which gives backward Newton’s interpolation formula for powers. For example, the formula gives the following expansions for cubes: \[\begin{align*} t=0, \quad n^3 &= 0 \tbinom{n-1}{0} + 1 \tbinom{n}{1} - 6 \tbinom{n+1}{2} + 6 \tbinom{n+2}{3}, \\ t=1, \quad n^3 &= 1 \tbinom{n-2}{0} + 1 \tbinom{n-1}{1} + 0 \tbinom{n}{2} + 6 \tbinom{n+1}{3}, \\ t=2, \quad n^3 &= 8 \tbinom{n-3}{0} + 7 \tbinom{n-2}{1} + 6 \tbinom{n-1}{2} + 6 \tbinom{n}{3}, \\ t=3, \quad n^3 &= 27 \tbinom{n-4}{0} + 19 \tbinom{n-3}{1} + 12 \tbinom{n-2}{2} + 6 \tbinom{n-1}{3}. \end{align*}\]
The transition to a formula for sums of powers is straightforward: \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{k=0}^{m} \left[ \sum_{j=1}^{n} \binom{j-t+k-1}{k} \right] \nabla^{k} t^m. \end{align*}\] Setting \(r=0\) in Lemma [lem:backward-hockey-stick-identity] therefore 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\), the following identity holds \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+k}{k+1} - \binom{k-t}{k+1} \right] \nabla^{k} t^m. \end{align*}\]
The basis \(\binom{j-t+k-1+r}{k+r}\) is well suited to repeated applications of Lemma [lem:backward-hockey-stick-identity]. Indeed, setting the parameter \(r\) gives a closed form for sums of powers. For example, the case of cubes is as follows:
Example 11. For integers \(t\) with \(0 \le t \le 7\), we have \[\begin{align*} \Sigma^{1}\,{n}^{3} &= 0 \cdot \!\left[\tbinom{n}{1}-\tbinom{0}{1}\right] + 1 \cdot \!\left[\tbinom{n+1}{2}-\tbinom{1}{2}\right] - 6 \cdot \!\left[\tbinom{n+2}{3}-\tbinom{2}{3}\right] + 6 \cdot \!\left[\tbinom{n+3}{4}-\tbinom{3}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 1 \cdot \!\left[\tbinom{n-1}{1}-\tbinom{-1}{1}\right] + 1 \cdot \!\left[\tbinom{n}{2}-\tbinom{0}{2}\right] + 0 \cdot \!\left[\tbinom{n+1}{3}-\tbinom{1}{3}\right] + 6 \cdot \!\left[\tbinom{n+2}{4}-\tbinom{2}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 8 \cdot \!\left[\tbinom{n-2}{1}-\tbinom{-2}{1}\right] + 7 \cdot \!\left[\tbinom{n-1}{2}-\tbinom{-1}{2}\right] + 6 \cdot \!\left[\tbinom{n}{3}-\tbinom{0}{3}\right] + 6 \cdot \!\left[\tbinom{n+1}{4}-\tbinom{1}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 27 \cdot \!\left[\tbinom{n-3}{1}-\tbinom{-3}{1}\right] + 19 \cdot \!\left[\tbinom{n-2}{2}-\tbinom{-2}{2}\right] + 12 \cdot \!\left[\tbinom{n-1}{3}-\tbinom{-1}{3}\right] + 6 \cdot \!\left[\tbinom{n}{4}-\tbinom{0}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 64 \cdot \!\left[\tbinom{n-4}{1}-\tbinom{-4}{1}\right] + 37 \cdot \!\left[\tbinom{n-3}{2}-\tbinom{-3}{2}\right] + 18 \cdot \!\left[\tbinom{n-2}{3}-\tbinom{-2}{3}\right] + 6 \cdot \!\left[\tbinom{n-1}{4}-\tbinom{-1}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 125 \cdot \!\left[\tbinom{n-5}{1}-\tbinom{-5}{1}\right] + 61 \cdot \!\left[\tbinom{n-4}{2}-\tbinom{-4}{2}\right] + 24 \cdot \!\left[\tbinom{n-3}{3}-\tbinom{-3}{3}\right] + 6 \cdot \!\left[\tbinom{n-2}{4}-\tbinom{-2}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 216 \cdot \!\left[\tbinom{n-6}{1}-\tbinom{-6}{1}\right] + 91 \cdot \!\left[\tbinom{n-5}{2}-\tbinom{-5}{2}\right] + 30 \cdot \!\left[\tbinom{n-4}{3}-\tbinom{-4}{3}\right] + 6 \cdot \!\left[\tbinom{n-3}{4}-\tbinom{-3}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 343 \cdot \!\left[\tbinom{n-7}{1}-\tbinom{-7}{1}\right] + 127 \cdot \!\left[\tbinom{n-6}{2}-\tbinom{-6}{2}\right] + 36 \cdot \!\left[\tbinom{n-5}{3}-\tbinom{-5}{3}\right] + 6 \cdot \!\left[\tbinom{n-4}{4}-\tbinom{-4}{4}\right]. \end{align*}\]
In the preceding example, some binomial coefficients have negative upper indices, which may look unfamiliar. These coefficients are well defined because they satisfy the upper negation identity for binomial coefficients \(\binom{-n}{k} = (-1)^{k} \binom{k+n-1}{k}\) in Lemma [lem:upper-binomial-negation]. Thus, \[\begin{align*} \binom{k-t}{k+1} = \binom{-(t+k)}{k+1} = (-1)^{k+1} \binom{(k+1)+(t-k)-1}{k+1} = (-1)^{k+1} \binom{t}{k+1} \end{align*}\]
Corollary 12 (Ordinary Sums of Powers). For non-negative integers \(n\) and \(m\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \Sigma^{1}\,{n}^{m} &= \sum_{k=0}^{m} \left[ \binom{n-t+k}{k+1} + (-1)^{k+2} \binom{t}{k+1} \right] \nabla^{k} t^m \\ &= \sum_{k=0}^{m} \left[ \binom{n-t+k}{k+1} + (-1)^{k} \binom{t}{k+1} \right] \nabla^{k} t^m. \end{align*}\]
For example,
Example 13. For integers \(t\) with \(0 \le t \le 7\), we have \[\begin{align*} \Sigma^{1}\,{n}^{3} &= 0 \cdot \!\left[\tbinom{n}{1}+\tbinom{0}{1}\right] + 1 \cdot \!\left[\tbinom{n+1}{2}-\tbinom{0}{2}\right] + 6 \cdot \!\left[\tbinom{n+2}{3}+\tbinom{0}{3}\right] + 6 \cdot \!\left[\tbinom{n+3}{4}-\tbinom{0}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 1 \cdot \!\left[\tbinom{n-1}{1}+\tbinom{1}{1}\right] + 1 \cdot \!\left[\tbinom{n-0}{2}-\tbinom{1}{2}\right] + 0 \cdot \!\left[\tbinom{n+1}{3}+\tbinom{1}{3}\right] + 6 \cdot \!\left[\tbinom{n+2}{4}-\tbinom{1}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 8 \cdot \!\left[\tbinom{n-2}{1}+\tbinom{2}{1}\right] + 7 \cdot \!\left[\tbinom{n-1}{2}-\tbinom{2}{2}\right] + 6 \cdot \!\left[\tbinom{n-0}{3}+\tbinom{2}{3}\right] + 6 \cdot \!\left[\tbinom{n+1}{4}-\tbinom{2}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 27 \cdot \!\left[\tbinom{n-3}{1}+\tbinom{3}{1}\right] + 19 \cdot \!\left[\tbinom{n-2}{2}-\tbinom{3}{2}\right] + 12 \cdot \!\left[\tbinom{n-1}{3}+\tbinom{3}{3}\right] + 6 \cdot \!\left[\tbinom{n-0}{4}-\tbinom{3}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 64 \cdot \!\left[\tbinom{n-4}{1}+\tbinom{4}{1}\right] + 37 \cdot \!\left[\tbinom{n-3}{2}-\tbinom{4}{2}\right] + 18 \cdot \!\left[\tbinom{n-2}{3}+\tbinom{4}{3}\right] + 6 \cdot \!\left[\tbinom{n-1}{4}-\tbinom{4}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 125 \cdot \!\left[\tbinom{n-5}{1}+\tbinom{5}{1}\right] + 61 \cdot \!\left[\tbinom{n-4}{2}-\tbinom{5}{2}\right] + 24 \cdot \!\left[\tbinom{n-3}{3}+\tbinom{5}{3}\right] + 6 \cdot \!\left[\tbinom{n-2}{4}-\tbinom{5}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 216 \cdot \!\left[\tbinom{n-6}{1}+\tbinom{6}{1}\right] + 91 \cdot \!\left[\tbinom{n-5}{2}-\tbinom{6}{2}\right] + 30 \cdot \!\left[\tbinom{n-4}{3}+\tbinom{6}{3}\right] + 6 \cdot \!\left[\tbinom{n-3}{4}-\tbinom{6}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 343 \cdot \!\left[\tbinom{n-7}{1}+\tbinom{7}{1}\right] + 127 \cdot \!\left[\tbinom{n-6}{2}-\tbinom{7}{2}\right] + 36 \cdot \!\left[\tbinom{n-5}{3}+\tbinom{7}{3}\right] + 6 \cdot \!\left[\tbinom{n-4}{4}-\tbinom{7}{4}\right]. \end{align*}\]
Moreover, the binomial coefficient \(\binom{n}{k}\) is a polynomial in \(n\) and therefore accepts fractional values in its upper index. Consequently, the expression in Proposition [prop:ordinary-sums-of-powers] is also a polynomial in \(n\). The following example illustrates the polynomial form of the formula.
Example 14. For integers \(t\) with \(0 \leq t \leq 4\), we have \[\begin{align*} t=0, \quad \Sigma^{1}\,{n}^{3} &= n \cdot 0 + \tfrac{1}{2}(n+n^2)\cdot 1 \\ &+ \tfrac{1}{6}(2n+3n^2+n^3)\cdot(-6) \\ &+ \tfrac{1}{24}(6n+11n^2+6n^3+n^4)\cdot 6, \\ t=1, \quad \Sigma^{1}\,{n}^{3} &= n \cdot 1 + \tfrac{1}{2}(-n+n^2)\cdot 1 \\ &+ \tfrac{1}{6}(-n+n^3)\cdot 0 \\ &+ \tfrac{1}{24}(-2n-n^2+2n^3+n^4)\cdot 6, \\ t=2, \quad \Sigma^{1}\,{n}^{3} &= n \cdot 8 + \tfrac{1}{2}(-3n+n^2)\cdot 7 \\ &+ \tfrac{1}{6}(2n-3n^2+n^3)\cdot 6 \\ &+ \tfrac{1}{24}(2n-n^2-2n^3+n^4)\cdot 6, \\ t=3, \quad \Sigma^{1}\,{n}^{3} &= n \cdot 27 + \tfrac{1}{2}(-5n+n^2)\cdot 19 \\ &+ \tfrac{1}{6}(11n-6n^2+n^3)\cdot 12 \\ &+ \tfrac{1}{24}(-6n+11n^2-6n^3+n^4)\cdot 6, \\ t=4, \quad \Sigma^{1}\,{n}^{3} &= n \cdot 64 + \tfrac{1}{2}(-7n+n^2)\cdot 37 \\ &+ \tfrac{1}{6}(26n-9n^2+n^3)\cdot 18 \\ &+ \tfrac{1}{24}(-50n+35n^2-10n^3+n^4)\cdot 6. \end{align*}\]
The coefficients for the indicated values of \(t\) form the following OEIS sequences:
For \(t=0\), the coefficients
\(0, 1, -6, 6\) form sequence A278075 in the
OEIS (Sloane, Neil
J.A. and others 2003).
For \(t=1\), the coefficients
\(1, 1, 0, 6\) form sequence A389570 in the
OEIS (Sloane, Neil
J.A. and others 2003).
For \(t=2\), the coefficients
\(8, 7, 6, 6\) form sequence A391068 in the
OEIS (Sloane, Neil
J.A. and others 2003).
For \(t=3\), the coefficients
\(27, 19, 12, 6\) form sequence A391210 in the
OEIS (Sloane, Neil
J.A. and others 2003).
For \(t=4\), the coefficients
\(64, 37, 18, 6\) form sequence A395604 in the
OEIS (Sloane, Neil
J.A. and others 2003).
We derive a formula for double sums of powers similarly. Setting \(r=1\) in Lemma [lem:backward-hockey-stick-identity] yields the following result.
Proposition 15 (Double Sums of Powers). For non-negative integers \(n\) and \(m\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n-t+k+1}{k+2} - \binom{k-t+1}{k+2} \Sigma^{0}\,{n}^{0} - \binom{k-t+0}{k+1} \Sigma^{1}\,{n}^{0} \right] \nabla^{k} t^m. \end{align*}\]
The formula includes the correction terms \(\Sigma^{0}\,{n}^{0}=1\) and \(\Sigma^{1}\,{n}^{0}=n\). The next example gives a formula for double sums of powers.
Example 16. For integers \(t\) with \(0 \leq t \leq 2\), we have \[\begin{align*} t=0, \quad \Sigma^{2}\,{n}^{3} &= \tfrac{1}{2}(n+n^2)\cdot0 +\tfrac{1}{6}(2n+3n^2+n^3)\cdot1 +\tfrac{1}{24}(6n+11n^2+6n^3+n^4)\cdot(-6) \\ &+\tfrac{1}{120}(24n+50n^2+35n^3+10n^4+n^5)\cdot6, \\ t=1, \quad \Sigma^{2}\,{n}^{3} &= \tfrac{1}{2}(n+n^2)\cdot1 +\tfrac{1}{6}(-n+n^3)\cdot1 +\tfrac{1}{24}(-2n-n^2+2n^3+n^4)\cdot0 \\ &+\tfrac{1}{120}(-6n-5n^2+5n^3+5n^4+n^5)\cdot6, \\ t=2, \quad \Sigma^{2}\,{n}^{3} &= \tfrac{1}{2}(n+n^2)\cdot8 +\tfrac{1}{6}(-4n-3n^2+n^3)\cdot7 +\tfrac{1}{24}(2n-n^2-2n^3+n^4)\cdot6 \\ &+\tfrac{1}{120}(4n-5n^3+n^5)\cdot6. \end{align*}\]
Similarly, repeated application of Lemma [lem:backward-hockey-stick-identity] yields a closed formula for multifold sums of powers.
Theorem 17 (Multifold Sums of Powers). For non-negative integers \(r\), \(n\), and \(m\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \Sigma^{r+1}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n+k+r-t}{k+r+1} - \sum_{s=0}^{r} \binom{k-s+r-t}{k-s+r+1} \Sigma^{s}\,{n}^{0} \right] \nabla^{k} t^{m}. \end{align*}\]
The following example illustrates the multifold formula.
Example 18. For non-negative integers \(r\), \(n\), and \(m\), we have \[\begin{align*} \Sigma^{r+1}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-0}{k+r+1} - \mathop{\textstyle\sum}_{s=0}^{r} \tbinom{k-s+r-0}{k-s+r+1} \Sigma^{s}\,{n}^{0} \right] \nabla^{k} 0^{m}, \\ \Sigma^{r+1}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-1}{k+r+1} - \mathop{\textstyle\sum}_{s=0}^{r} \tbinom{k-s+r-1}{k-s+r+1} \Sigma^{s}\,{n}^{0} \right] \nabla^{k} 1^{m}, \\ \Sigma^{r+1}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-2}{k+r+1} - \mathop{\textstyle\sum}_{s=0}^{r} \tbinom{k-s+r-2}{k-s+r+1} \Sigma^{s}\,{n}^{0} \right] \nabla^{k} 2^{m}, \\ \Sigma^{r+1}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-3}{k+r+1} - \mathop{\textstyle\sum}_{s=0}^{r} \tbinom{k-s+r-3}{k-s+r+1} \Sigma^{s}\,{n}^{0} \right] \nabla^{k} 3^{m}, \\ \Sigma^{r+1}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-4}{k+r+1} - \mathop{\textstyle\sum}_{s=0}^{r} \tbinom{k-s+r-4}{k-s+r+1} \Sigma^{s}\,{n}^{0} \right] \nabla^{k} 4^{m}. \end{align*}\]
Using Lemma [lem:multifold-sum-of-zero-powers], we obtain the following binomial form of Theorem [thm:multifold-sums-of-powers].
Proposition 19 (Multifold Binomial Sums of Powers). For non-negative integers \(r\), \(n\), and \(m\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \Sigma^{r+1}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n+k+r-t}{k+r+1} - \sum_{s=0}^{r} \binom{k-s+r-t}{k-s+r+1} \binom{s+n-1}{s} \right] \nabla^{k} t^{m}. \end{align*}\]
Replacing \(t\) with \(-t\) yields another formula for multifold sums of powers.
Proposition 20 (Multifold Binomial Sums of Powers Negated). For non-negative integers \(r\), \(n\), and \(m\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \Sigma^{r+1}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n+k+r+t}{k+r+1} - \sum_{s=0}^{r} \binom{k-s+r+t}{k-s+r+1} \binom{s+n-1}{s} \right] \nabla^{k} (-t)^{m}. \end{align*}\]
The next example illustrates the formula after replacing \(t\) with \(-t\).
Example 21. For integers \(t\) with \(1 \leq t \leq 4\), we have \[\begin{align*} t=1, \quad \Sigma^{1}\,{n}^{3} &= n \cdot (-1) + \tfrac{1}{2}(3n+n^2)\cdot 7 + \tfrac{1}{6}(11n+6n^2+n^3)\cdot (-12) \\ &+ \tfrac{1}{24}(50n+35n^2+10n^3+n^4)\cdot 6, \\ t=2, \quad \Sigma^{1}\,{n}^{3} &= n \cdot (-8) + \tfrac{1}{2}(5n+n^2)\cdot 19 + \tfrac{1}{6}(26n+9n^2+n^3)\cdot (-18) \\ &+ \tfrac{1}{24}(154n+71n^2+14n^3+n^4)\cdot 6, \\ t=3, \quad \Sigma^{1}\,{n}^{3} &= n \cdot (-27) + \tfrac{1}{2}(7n+n^2)\cdot 37 + \tfrac{1}{6}(47n+12n^2+n^3)\cdot (-24) \\ &+ \tfrac{1}{24}(342n+119n^2+18n^3+n^4)\cdot 6, \\ t=4, \quad \Sigma^{1}\,{n}^{3} &= n \cdot (-64) + \tfrac{1}{2}(9n+n^2)\cdot 61 + \tfrac{1}{6}(74n+15n^2+n^3)\cdot (-30) \\ &+ \tfrac{1}{24}(638n+179n^2+22n^3+n^4)\cdot 6. \end{align*}\]
The following lemma relates Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\) to backward differences of powers \(\nabla^{k} t^{m}\).
Lemma 22 (Stirling Backward Differences). For non-negative integers \(m\) and \(k\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \nabla^{k} t^{m} = \sum_{j=k}^{m} \binom{t-k}{j-k} \genfrac{\{}{\}}{0pt}{}{m}{j} j!. \end{align*}\]
Proof. The identity \(t^m = \sum_{k=0}^{m} \binom{t}{k} \genfrac{\{}{\}}{0pt}{}{m}{k} k!\), together with the binomial recurrence \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\), gives the result. ◻
The lemma gives the following representation.
Proposition 23 (Multifold Stirling Sums of Powers). For non-negative integers \(r\), \(n\), and \(m\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \Sigma^{r+1}\,{n}^{m} = \sum_{k=0}^{m} \sum_{j=k}^{m} \left[ \binom{n+k+r-t}{k+r+1} - \sum_{s=0}^{r} \binom{k-s+r-t}{k-s+r+1} \binom{s+n-1}{s} \right] \binom{t-k}{j-k} \genfrac{\{}{\}}{0pt}{}{m}{j} j! \end{align*}\]
The following lemma relates Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\) to backward differences of powers \(\nabla^{k} t^{m}\).
Lemma 24 (Eulerian Backward Differences). For non-negative integers \(m\) and \(k\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \nabla^{k} t^{m} = \sum_{j=0}^{m} \binom{t+j-k}{m-k} \genfrac{\langle}{\rangle}{0pt}{}{m}{j}. \end{align*}\]
Proof. Worpitzky’s identity \(t^{m} = \sum_{k=0}^{m} \binom{t+k}{m} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}\), together with the binomial recurrence \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\), gives the result. See (Worpitzky 1883). ◻
The lemma gives the following representation.
Proposition 25 (Multifold Eulerian Sums of Powers). For non-negative integers \(r\), \(n\), and \(m\), and an arbitrary integer \(t\), the following identity holds \[\begin{align*} \Sigma^{r+1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n+k+r-t}{k+r+1} - \sum_{s=0}^{r} \binom{k-s+r-t}{k-s+r+1} \binom{s+n-1}{s} \right] \binom{t+j-k}{m-k} \genfrac{\langle}{\rangle}{0pt}{}{m}{j}. \end{align*}\]
In this manuscript, we derive closed formulas for multifold sums of powers of integers by combining the backward 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.
Use the GitHub
repository to validate the results using Mathematica programs. Table 1 lists the programs and
the results they validate.
| Mathematica Function | Validates or Prints |
|---|---|
ValidateBackwardNewtonsFormulaForPowers.txt |
Validates Lemma [lem:backward-newtons-formula-for-powers] |
ValidateOrdinarySumsOfPowers.txt |
Validates Proposition [prop:ordinary-sums-of-powers] |
ValidateDoubleSumsOfPowers.txt |
Validates Proposition [prop:double-sums-of-powers] |
ValidateMultifoldSumsOfPowers.txt |
Validates Theorem [thm:multifold-sums-of-powers] |
ValidateMultifoldBinomialSumsOfPowers.txt |
Validates Proposition [prop:multifold-binomial-sums-of-powers] |
ValidateMultifoldBinomialSumsOfPowersNegated.txt |
Validates Proposition [prop:multifold-binomial-sums-of-powers-negated] |
ValidateMultifoldEulerianSumsOfPowers.txt |
Validates Proposition [prop:multifold-eulerian-sums-of-powers] |
ValidateMultifoldStirlingSumsOfPowers.txt |
Validates Proposition [prop:multifold-stirling-sums-of-powers] |
Metadata
Initial release date: January 1, 2026.
Current release date: 2026-11-12.
Version:
2.2.0+main.173b9e9
MSC2010: 05A19, 05A10, 11B73, 11B83 .
Keywords: Sums of powers, Newton’s interpolation formula, Finite differences, Binomial coefficients, Faulhaber’s formula, Bernoulli numbers, Bernoulli polynomials, Interpolation, Approximation, Discrete convolution, Combinatorics, Polynomial identities, Central factorial numbers, Stirling numbers, Eulerian numbers, Worpitzky identity, Pascal’s triangle, OEIS .
License: This work is licensed under a CC BY 4.0 License.
Web Version: kolosovpetro.github.io/sums-of-powers-backward-differences
Sources: github/kolosovpetro/SumsOfPowersBackwardDiffNewtonFormula
ORCID: 0000-0002-6544-8880
Email: kolosovp94@gmail.com