Sums of Powers via Backward Finite Differences and Newton’s Formula

Petro Kolosov

2026-11-12

Abstract

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.

Preliminaries

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.

  1. When \(r=0\), Definition 1 gives \(\Sigma^{0}\,{n}^{0} = 1\).

  2. When \(r=1\), we have \(\Sigma^{1}\,{n}^{0} = \sum_{k=1}^{n} 1 = \binom{n}{1}\).

  3. When \(r=2\), we have \(\Sigma^{2}\,{n}^{0} = \sum_{k=1}^{n} \binom{k}{1} = \binom{n+1}{2}\).

  4. When \(r=3\), we have \(\Sigma^{3}\,{n}^{0} = \sum_{k=1}^{n} \binom{k+1}{2} = \binom{n+2}{3}\).

  5. 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).

Introduction

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].

Main Results

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:

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*}\]

Stirling Form

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*}\]

Eulerian Form

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*}\]

Conclusions

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.

Mathematica Programs

Use the GitHub repository to validate the results using Mathematica programs. Table 1 lists the programs and the results they validate.

Mathematica 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

Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren. 1994. Concrete mathematics: A foundation for computer science (second edition). Https://archive.org/details/concrete-mathematics; Addison-Wesley Publishing Company, Inc.
Knuth, Donald E. 1992. Two Notes on Notation. https://arxiv.org/abs/math/9205211.
Knuth, Donald E. 1993. “Johann Faulhaber and sums of powers.” Mathematics of Computation 61 (203): 277–94. https://arxiv.org/abs/math/9207222.
Kolosov, Petro. 2026. Sums of Powers of Integers: A Complete Framework for Closed Formulas. Zenodo. https://doi.org/10.5281/zenodo.20548019.
Newton, Isaac and Chittenden, N.W. 1850. Newton’s Principia: the mathematical principles of natural philosophy. Https://archive.org/details/bub_gb_KaAIAAAAIAAJ/page/466/mode/2up; New-York, D. Adee.
Sloane, Neil J.A. and others. 2003. The on-line encyclopedia of integer sequences. Https://oeis.org/.
Steffensen, J. F. 1933. “ON THE DEFINITION OF THE CENTRAL FACTORIAL.” Journal of the Institute of Actuaries (1886-1994) 64 (2): 165–68. http://www.jstor.org/stable/41137516.
Steffensen, Johan Frederik. 1927. Interpolation. Https://www.amazon.com/-/de/Interpolation-Second-Dover-Books-Mathematics-ebook/dp/B00GHQVON8; Williams & Wilkins.
Worpitzky, J. 1883. “Studien Über Die Bernoullischen Und Eulerschen Zahlen.” Journal Für Die Reine Und Angewandte Mathematik 94: 203–32. http://eudml.org/doc/148532.