Newton’s Interpolation Formula and Sums of Powers

Petro Kolosov

2026-11-07

Abstract

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.

Auxiliary Lemmas

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.

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

  2. When \(r=1\), \(\Sigma^{1}\,{n}^{0} = \mathop{\textstyle\sum}_{k=1}^{n} 1 = \tbinom{n}{1}\).

  3. When \(r=2\), \(\Sigma^{2}\,{n}^{0} = \mathop{\textstyle\sum}_{k=1}^{n} \tbinom{k}{1} = \tbinom{n+1}{2}\).

  4. When \(r=3\), \(\Sigma^{3}\,{n}^{0} = \mathop{\textstyle\sum}_{k=1}^{n} \tbinom{k+1}{2} = \tbinom{n+2}{3}\).

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

Introduction

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

Main Results

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.

Stirling Form

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

Eulerian Form

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

Backward Difference Form

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

Central Difference Form

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

Conclusions

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.

Acknowledgements

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.

Mathematica Programs

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 programs and the results they validate.
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

Cereceda, José L. 2022. “Sums of powers of integers and generalized Stirling numbers of the second kind.” arXiv preprint arXiv:2211.11648. https://arxiv.org/abs/2211.11648.
Graham, Ronald L., Donald E. Knuth, and Oren Patashnik. 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 N. W. Chittenden. 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.
Pfaff, Thomas J. 2007. “Deriving a Formula for Sums of Powers of Integers.” Pi Mu Epsilon Journal 12 (7): 425–30. https://www.jstor.org/stable/24340705.
Sloane, Neil J. A. et al. 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.