Sums of powers via backward finite differences and Newton’s formula

Petro Kolosov

2026-06-29

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.

Auxiliary lemmas

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 (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*}\] where \(\nabla^{k} f(t)\) is 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. 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-1}{k}\), we get binomial form. ◻

Lemma 4 (Backward 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-1}{k} \nabla^{k} t^m. \end{align*}\]

Proof. Special case of Lemma [lem:backward-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 (Backward hockey-stick identity). For integer \(n\geq1\), and arbitrary integers \(t,k,r\) \[\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. By setting \(a=k-t+r\), and \(b=n-t+k-1+r\) 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.

  1. Let \(r=0\), then we have \(\Sigma^{0}\,{n}^{0} = 1\), by definition [def:multifold-sums-of-powers-recurrence].

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

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

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

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

Introduction

In this manuscript, we derive formulas for sums of powers by combining backward Newton’s interpolation formula for powers [lem:backward-newtons-formula-for-powers] with hockey-stick identity [lem:backward-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{\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*}\] 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. Thus, we focus on closed forms of powers sums, by utilizing backward Newton’s formula, and hockey-stick identity [lem:backward-hockey-stick-identity].

Main results

We start our discussion from Lemma [lem:backward-newtons-formula-for-powers], which yields backward Newton’s interpolation formula for powers. For example, \[\begin{align*} n^3 &= 0 \tbinom{n-1}{0} + 1 \tbinom{n}{1} - 6 \tbinom{n+1}{2} + 6 \tbinom{n+2}{3}, \\ n^3 &= 1 \tbinom{n-2}{0} + 1 \tbinom{n-1}{1} + 0 \tbinom{n}{2} + 6 \tbinom{n+1}{3}, \\ n^3 &= 8 \tbinom{n-3}{0} + 7 \tbinom{n-2}{1} + 6 \tbinom{n-1}{2} + 6 \tbinom{n}{3}, \\ n^3 &= 27 \tbinom{n-4}{0} + 19 \tbinom{n-3}{1} + 12 \tbinom{n-2}{2} + 6 \tbinom{n-1}{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-1}{k} \right] \nabla^{k} t^m. \end{align*}\] Therefore, by setting \(r=0\) into Lemma [lem:backward-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+k}{k+1} - \binom{k-t}{k+1} \right] \nabla^{k} t^m. \end{align*}\]

We may see that the basis \(\binom{j-t+k-1+r}{k+r}\) for repeatedly applied Lemma [lem:backward-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 \le t \le 3\), we have \[\begin{align*} \Sigma^{1}\,{n}^{3} &= 0\!\left[\tbinom{n}{1}-\tbinom{0}{1}\right] + 1\!\left[\tbinom{n+1}{2}-\tbinom{1}{2}\right] - 6\!\left[\tbinom{n+2}{3}-\tbinom{2}{3}\right] + 6\!\left[\tbinom{n+3}{4}-\tbinom{3}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 1\!\left[\tbinom{n-1}{1}-\tbinom{-1}{1}\right] + 1\!\left[\tbinom{n}{2}-\tbinom{0}{2}\right] + 0\!\left[\tbinom{n+1}{3}-\tbinom{1}{3}\right] + 6\!\left[\tbinom{n+2}{4}-\tbinom{2}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 8\!\left[\tbinom{n-2}{1}-\tbinom{-2}{1}\right] + 7\!\left[\tbinom{n-1}{2}-\tbinom{-1}{2}\right] + 6\!\left[\tbinom{n}{3}-\tbinom{0}{3}\right] + 6\!\left[\tbinom{n+1}{4}-\tbinom{1}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 27\!\left[\tbinom{n-3}{1}-\tbinom{-3}{1}\right] + 19\!\left[\tbinom{n-2}{2}-\tbinom{-2}{2}\right] + 12\!\left[\tbinom{n-1}{3}-\tbinom{-1}{3}\right] + 6\!\left[\tbinom{n}{4}-\tbinom{0}{4}\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}\). Moreover, binomial coefficient \(\binom{n}{k}\) is a polynomial in \(n\), thus accepting even fraction values in its upper index. Therefore, Proposition [prop:ordinary-sums-of-powers] is also a polynomial in \(n\). For example,

Example 12. For integer \(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*}\]

Where the coefficients

Formula for double sums of powers could be derivate similarly, by setting \(r=1\) into Lemma [lem:backward-hockey-stick-identity] which yields

Proposition 13 (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+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*}\]

Note that we added correction terms \(\Sigma^{r}\,{n}^{0}\), which are \(\Sigma^{0}\,{n}^{0}=1\), and \(\Sigma^{1}\,{n}^{0}=n\). For example,

Example 14. For integer \(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, we obtain closed formula for multifold sums of powers, by using Lemma [lem:backward-hockey-stick-identity] repeatedly. Thus,

Theorem 15 (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+k+r-1}{k+r} - \sum_{s=0}^{r-1} \binom{k-t+r-1-s}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \nabla^{k} t^{m}. \end{align*}\]

For example,

Example 16. For non-negative integers \(r,n,m\) we have \[\begin{align*} \Sigma^{r}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-1}{k+r} - \mathop{\textstyle\sum}_{s=0}^{r-1} \tbinom{k+r-1-s}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \nabla^k 0^m, \\ \Sigma^{r}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-2}{k+r} - \mathop{\textstyle\sum}_{s=0}^{r-1} \tbinom{k+r-2-s}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \nabla^k 1^m, \\ \Sigma^{r}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-3}{k+r} - \mathop{\textstyle\sum}_{s=0}^{r-1} \tbinom{k+r-3-s}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \nabla^k 2^m, \\ \Sigma^{r}\,{n}^{m} &= \mathop{\textstyle\sum}_{k=0}^{m} \left[ \tbinom{n+k+r-4}{k+r} - \mathop{\textstyle\sum}_{s=0}^{r-1} \tbinom{k+r-4-s}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \nabla^k 3^m. \end{align*}\]

By using Lemma [lem:multifold-sum-of-zero-powers], we get pure binomial version of Theorem [thm:multifold-sums-of-powers]

Proposition 17 (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+k+r-1}{k+r} - \sum_{s=0}^{r-1} \binom{k-t+r-1-s}{k+r-s} \binom{s+n-1}{s} \right] \nabla^{k} t^{m}. \end{align*}\]

By setting \(t \rightarrow -t\) yields another remarkable formula for multifold sums of powers of integers. Therefore,

Proposition 18 (Multifold Binomial sums of powers negated). 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+k+r-1}{k+r} - \sum_{s=0}^{r-1} \binom{k+t+r-1-s}{k+r-s} \binom{s+n-1}{s} \right] \nabla^{k} (-t)^{m}. \end{align*}\]

For example,

Example 19. For integer \(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

We have Lemma which connects Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\) with backward differences of powers \(\nabla^{k} t^{m}\)

Lemma 20 (Stirling Backward differences). For non-negative integers \(m,k\), and an arbitrary integer \(t\) \[\begin{align*} \nabla^{k} t^{m} = \sum_{j=k}^{m} \binom{t-k}{j-k} \genfrac{\{}{\}}{0pt}{}{m}{j} j! \end{align*}\]

Proof. By the identity \(t^m = \sum_{k=0}^{m} \binom{t}{k} \genfrac{\{}{\}}{0pt}{}{m}{k} k!\), and by using binomial recurrence \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\). ◻

Therefore,

Proposition 21 (Multifold Stirling 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} \sum_{j=k}^{m} \left[ \binom{n-t+k+r-1}{k+r} - \sum_{s=0}^{r-1} \tbinom{k-t+r-1-s}{k+r-s} \tbinom{s+n-1}{s} \right] \binom{t-k}{j-k} \genfrac{\{}{\}}{0pt}{}{m}{j} j! \end{align*}\]

Eulerian form

We have Lemma which connects Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\) with backward differences of powers \(\nabla^{k} t^{m}\)

Lemma 22 (Eulerian Backward differences). For non-negative integers \(m,k\), and an arbitrary integer \(t\) \[\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. By Worpitzky identity \(t^{m} = \sum_{k=0}^{m} \binom{t+k}{m} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}\), and by binomial recurrence \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\), see (Worpitzky 1883). ◻

Therefore,

Proposition 23 (Multifold Eulerian 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} \sum_{j=0}^{m} \left[ \binom{n-t+k+r-1}{k+r} - \sum_{s=0}^{r-1} \tbinom{k-t+r-1-s}{k+r-s} \tbinom{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 this GitHub repository to validate the results using Mathematica programs.

Mathematica Function Validates / Prints
ValidateBackwardNewtonsFormulaForPowers.txt Validates Lem. [lem:backward-newtons-formula-for-powers]
ValidateOrdinarySumsOfPowers.txt Validates Prop. [prop:ordinary-sums-of-powers]
ValidateDoubleSumsOfPowers.txt Validates Prop. [prop:double-sums-of-powers]
ValidateMultifoldSumsOfPowers.txt Validates Thm. [thm:multifold-sums-of-powers]
ValidateMultifoldBinomialSumsOfPowers.txt Validates Prop. [prop:multifold-binomial-sums-of-powers]
ValidateMultifoldBinomialSumsOfPowersNegated.txt Validates Prop. [prop:multifold-binomial-sums-of-powers-negated]
ValidateMultifoldEulerianSumsOfPowers.txt Validates Prop. [prop:multifold-eulerian-sums-of-powers]
ValidateMultifoldStirlingSumsOfPowers.txt Validates Prop. [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.