2026-01-24
We derive formulas for sums of powers via Newton’s interpolation formula based on backward finite differences of powers. In addition, we note that backward differences are closely related to Eulerian numbers, and Stirling numbers of the second kind. Thus, we express formulas for sums of powers in terms of Eulerian numbers, and Stirling numbers of the second kind.
In this manuscript, we derive formulas for multifold sums of powers by utilizing Newton’s interpolation formula. Furthermore, we provide formulas for multifold sums of powers in terms of Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\) and Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\). The main idea is to utilize Newton’s interpolation formula combined with hockey stick identities to derive formulas for multifold sums of powers. In this work, we use Newton’s interpolation formula in backward finite differences. However, Newton’s formula approach for sums of powers is quite generic, as such it does not necessary requires to bind to forward difference operator specifically. Thus, formulas for sums of powers using forward and central differences can be found in (Kolosov 2025a, 2025b), respectively. Define multifold sums of powers in Knuth’s (Knuth, Donald E. 1993) notation
Proposition 1 (Multifold sums of powers recurrence). For integers \(r,n,m \geq 0\), \[\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*}\]
Steffensen gives Newton’s formula for backward differences evaluated at zero \[\begin{align*} f(x) = \sum_{k=0}^{n} \binom{x+k-1}{k} \nabla^{k} f(0) \end{align*}\] in his book Interpolation (Steffensen, Johan Frederik 1927, chap. 2, eq. (19)). Thus, Newton’s formula for backward differences evaluated at arbitrary integer \(a\) follows.
Proposition 2 (Newton formula in backward differences). Let \(f\colon \mathbb{Z} \to \mathbb{C}\) be a function, and let \(a \in \mathbb{Z}\). Then, for all \(x \in \mathbb{Z}\), \[\begin{align*} f(x) &= \sum_{k=0}^{n} \binom{x-a+k-1}{k} \nabla^{k} f(a), \end{align*}\] where the \(k\)-th backward finite difference of \(f\) evaluated at \(a\) is defined by \[\begin{align*} \nabla^{k} f(a) = \sum_{j=0}^{k} (-1)^{j} \binom{k}{j} f(a-j). \end{align*}\]
Thus, by setting \(f(n)=n^m\), we get interpolation of powers via backward differences evaluated at arbitrary point \(t\).
Corollary 3 (Backward Newton’s formula for powers). For integers \(n,m \geq 0\), \[\begin{align*} n^m &= \sum_{j=0}^{m} \binom{n-t+j-1}{j} \nabla^{j} t^{m}, \end{align*}\] where \(\nabla^{j} t^{m} = \sum_{k=0}^{j} (-1)^{k} \binom{j}{k} (t-k)^{m}\).
Therefore, by Corollary [corr:backward-netwons-formula-for-powers], identity for sums of powers follows. \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \nabla^{j} t^{m} \sum_{k=1}^{n} \binom{k-t+j-1}{j}. \end{align*}\] We notice that the sum \(\sum_{k=1}^{n} \binom{k-t+j-1}{j}\) is a good candidate for hockey stick identity for binomial coefficients \(\sum_{k=0}^{n} \binom{k}{j} = \binom{n+1}{j+1}\). Thus, by setting \(a=j-t\) and \(b=j-t-1+n\), we get, \[\begin{align*} \sum_{k=1}^{n} \binom{k-t+j-1}{j} = \sum_{m=j-t}^{j-t-1+n} \binom{m}{j} = \binom{j-t+n}{j+1} - \binom{j-t}{j+1}. \end{align*}\] The closed form above is a partial case of Generalized hockey stick identity. That is,
Lemma 4 (Generalized hockey stick identity). For integers \(a \leq b\) and \(j\), \[\begin{align*} \sum_{m=a}^{b} \binom{m}{j} = \binom{b+1}{j+1} - \binom{a}{j+1}. \end{align*}\]
Proof. We have, \[\begin{align*} \mathop{\textstyle\sum}_{k=a}^{b} \tbinom{k}{j} = \tbinom{a}{j} + \tbinom{a+1}{j} + \cdots + \tbinom{b}{j}, \end{align*}\] which implies, \[\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). \end{align*}\] Thus, by hockey stick identity \(\mathop{\textstyle\sum}_{k=0}^{n} \binom{k}{j} = \binom{n+1}{j+1}\), we get, \[\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 5 (Shifted hockey stick identity). For integers \(j,r \geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \sum_{k=1}^{n} \binom{j-t+k+r-1}{j+r} =\sum_{a=j-t+r}^{j-t+n+r-1} \binom{a}{j+r} = \binom{j-t+n+r}{j+r+1} - \binom{j-t+r}{j+r+1}. \end{align*}\]
Proposition 6 (Backward sums of powers). For integers \(n,m \geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{1}\,{n}^{m} &= \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ \binom{j-t+n}{j+1} - \binom{j-t}{j+1} \right]. \end{align*}\]
Recall the negation property of binomial coefficients \(\binom{-k}{j} = (-1)^j \binom{j+k-1}{j}\). Thus, formula for negated backward sums of powers follows.
Proposition 7 (Negated backward sums of powers). For integers \(n,m \geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{1}\,{n}^{m} &= \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ \binom{j-t+n}{j+1} + (-1)^j \binom{t}{j+1} \right]. \end{align*}\]
For example, by setting \(t=2\) and
\(m=1\), we get, \[\begin{align*}
\Sigma^{1}\,{n}^{1} &=
2\left[ -\tbinom{2}{1} + \tbinom{n-2}{1} \right]
+ 1\left[ \tbinom{2}{2} + \tbinom{n-1}{2} \right].
\end{align*}\] For \(m=2\):
\[\begin{align*}
\Sigma^{1}\,{n}^{2}
=
4\left[ -\tbinom{2}{1} + \tbinom{n-2}{1} \right]
+ 3\left[ \tbinom{2}{2} + \tbinom{n-1}{2} \right]
+ 2\left[ -\tbinom{2}{3} + \tbinom{n}{3} \right].
\end{align*}\] For \(m=3\):
\[\begin{align*}
\Sigma^{1}\,{n}^{3}
=
8\left[ -\tbinom{2}{1} + \tbinom{n-2}{1} \right]
+ 7\left[ \tbinom{2}{2} + \tbinom{n-1}{2} \right]
+ 6\left[ -\tbinom{2}{3} + \tbinom{n}{3} \right]
+ 6\left[ \tbinom{2}{4} + \tbinom{n+1}{4} \right].
\end{align*}\] For \(m=4\):
\[\begin{align*}
\Sigma^{1}\,{n}^{4}
&=
16\left[ -\tbinom{2}{1} + \tbinom{n-2}{1} \right]
+ 15\left[ \tbinom{2}{2} + \tbinom{n-1}{2} \right]
+ 14\left[ -\tbinom{2}{3} + \tbinom{n}{3} \right]
+ 12\left[ \tbinom{2}{4} + \tbinom{n+1}{4} \right] \\
& + 24\left[ -\tbinom{2}{5} + \tbinom{n+2}{5} \right].
\end{align*}\] The coefficients \(1, 2,
1, 4, 3, 2, 8, 7, 6, 6,\ldots\) is the sequence A391068 in the
OEIS (Sloane, Neil
J.A. and others 2003). The following Lemma connects the Eulerian
numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\)
and backward differences of powers.
Lemma 8 (Backward differences in Eulerian numbers). For integers \(j,m \geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \nabla^{j} t^{m} = \sum_{k=0}^{m} \binom{t+k-j}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}. \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). ◻
Thus, we get formula for ordinary sums of powers in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{m}{k}\).
Proposition 9 (Ordinary sums of powers in Eulerian numbers). For non-negative integers \(n,m\) and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{1}\,{n}^{m} &= \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ (-1)^j \binom{t}{j+1} + \binom{j-t+n}{j+1} \right] \binom{t+k-j}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k} \end{align*}\]
It is quite remarkable that having \(t=0\) yields formula for sums of powers in double binomial form, involving Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{m}{k}\).
Proposition 10 (Ordinary Eulerian sums of powers in zero). For non-negative integers \(n,m\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \binom{j+n}{j+1} \binom{k-j}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}. \end{align*}\]
Lemma 11 (Backward differences in Stirling numbers). For integers \(j,m \geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \nabla^{j} t^{m} = \sum_{k=j}^{m} \binom{t-j}{k-j} \genfrac{\{}{\}}{0pt}{}{m}{k} k! \end{align*}\]
Proof. By the identity \(t^m = \sum_{k=0}^{m} \binom{t}{k} \genfrac{\{}{\}}{0pt}{}{m}{k} k!\) and binomial recurrence \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\). ◻
Thus, let be a formula for ordinary sums of powers in terms of Stirling numbers \(\genfrac{\{}{\}}{0pt}{}{m}{k}\)
Proposition 12 (Ordinary sums of powers in Stirling numbers). For non-negative integers \(n,m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{1}\,{n}^{m} &= \sum_{j=0}^{m} \sum_{k=j}^{m} \left[ (-1)^j \binom{t}{j+1} + \binom{j-t+n}{j+1} \right] \binom{t-j}{k-j} \genfrac{\{}{\}}{0pt}{}{m}{k} k! \end{align*}\]
By setting \(t=0\) yields
Proposition 13 (Ordinary Stirling sums of powers in zero). For non-negative integers \(n,m\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=j}^{m} \binom{j+n}{j+1} \binom{-j}{k-j} \genfrac{\{}{\}}{0pt}{}{m}{k} k! \end{align*}\]
By upper negation property of binomial coefficients \(\binom{-k}{j} = (-1)^j \binom{j+k-1}{j}\), another binomial form for sums of powers follows.
Proposition 14 (Ordinary Stirling sums of powers in zero altered). For non-negative integers \(n,m\) \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=j}^{m} (-1)^{k-j} \binom{k-1}{j-1} \binom{j+n}{j+1} \genfrac{\{}{\}}{0pt}{}{m}{k} k! \end{align*}\]
Similarly to Proposition [prop:negated-backward-sums-of-powers], we can derive formula for double sums of powers. Thus, \[\begin{align*} \Sigma^{2}\,{n}^{m} &= \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ (-1)^j \binom{t}{j+1} \sum_{k=1}^{n} 1 + \sum_{k=1}^{n} \binom{j-t+k}{j+1} \right] \end{align*}\] By applying generalized hockey stick identity [lem:generalized-hockey-stick-identity], we obtain, \[\begin{align*} \sum_{k=1}^{n} \binom{j-t+k}{j+1} = \sum_{k=j-t+1}^{j-t+n} \binom{k}{j+1} = \binom{j-t+n+1}{j+2} - \binom{j-t+1}{j+2}. \end{align*}\] Therefore, we get closed form. \[\begin{align*} \Sigma^{2}\,{n}^{m} &= \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ (-1)^j \binom{t}{j+1} n + \left( \binom{j-t+n+1}{j+2} - \binom{j-t+1}{j+2} \right) \right]. \end{align*}\] By applying the identity for negative binomial coefficients \(\binom{-k}{j} = (-1)^j \binom{j+k-1}{j}\), we get, \[\begin{align*} \binom{-(t-j-1)}{j+2} = (-1)^{j+2} \binom{t}{j+2}. \end{align*}\] Hence,
Proposition 15 (Double sums of powers via backward differences). For non-negative integers \(n,m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{2}\,{n}^{m} &= \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ (-1)^j \binom{t}{j+1} n + (-1)^{j+1} \binom{t}{j+2} n^0 + \binom{j-t+n+1}{j+2} \right] \end{align*}\]
By applying the hockey stick identities [lem:generalized-hockey-stick-identity], and [lem:shifted-hockey-stick-identity] repeatedly, yields formula for \(r-\)fold sums of powers.
Theorem 16 (Multifold sums of powers via backward difference). For non-negative integers \(r,n,m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ \binom{j-t+n+r-1}{j+r} + \sum_{s=0}^{r-1} (-1)^{j+s} \binom{t}{j+s+1} \Sigma^{r-1-s}\,{n}^{0} \right]. \end{align*}\]
We may observe that,
Proposition 17 (Multifold sum of zero powers). For integers \(r \geq 0\), and \(n\geq 1\), \[\begin{align*} \Sigma^{r}\,{n}^{0} = \binom{r+n-1}{r}. \end{align*}\]
Proof.
Let \(r=0\), then \(\Sigma^{0}\,{n}^{0}=n^0=\binom{n-1}{0} = 1\), by definition.
Let \(r=1\), then \(\Sigma^{1}\,{n}^{0} = \sum_{k=1}^{n} \binom{k-1}{0} = \sum_{k=1}^{n} 1 = \binom{n}{1}\).
Let \(r=2\), then \(\Sigma^{2}\,{n}^{0}= \sum_{k=1}^{n} \binom{k}{1} = \sum_{k=1}^{n} k = \binom{n+1}{2}\).
Let \(r=3\), then \(\Sigma^{3}\,{n}^{0} = \sum_{k=1}^{n} \binom{k+1}{2} = \binom{n+2}{3}\).
By induction over \(r\) and hockey stick identity \(\sum_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1}\), the claim follows \(\Sigma^{r}\,{n}^{0} = \binom{r+n-1}{r}\).
This completes the proof. ◻
Hence, binomial form of formula for multifold sums of powers [theorem:multifold-sums-of-powers-via-backward-difference] follows.
Proposition 18 (Multifold sums of powers binomial form). For non-negative integers \(r,n,m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ \binom{j-t+n+r-1}{j+r} + \sum_{s=0}^{r-1} (-1)^{j+s} \binom{t}{j+s+1} \binom{r-s+n-2}{r-s-1} \right]. \end{align*}\]
By setting \(r \rightarrow r+1\) yields shifted version of the identity above.
Corollary 19 (Multifold sums of powers binomial form shifted). For non-negative integers \(r,n,m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r+1}\,{n}^{m} = \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ \binom{j-t+n+r}{j+r+1} + \sum_{s=0}^{r} (-1)^{j+s} \binom{t}{j+s+1} \binom{r-s+n-1}{r-s} \right]. \end{align*}\]
By Lemma [lem:backward-differences-in-stirling-numbers], we get formula for multifold sums of powers in terms of Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\).
Proposition 20 (Multifold sums of powers in Stirling numbers). For non-negative integers \(r,n,m\) and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r+1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=j}^{m} \left[ \tbinom{j-t+n+r}{j+r+1} + \sum_{s=0}^{r} (-1)^{j+s} \tbinom{t}{j+s+1} \tbinom{r-s+n-1}{r-s} \right] \tbinom{t-j}{k-j} % {\textstyle\genfrac\{\}{0pt}{}{m}{k}}% k! \end{align*}\]
By lemma [lem:backward-differences-in-eulerian-numbers], we get formula for multifold sums of powers in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\).
Proposition 21 (Multifold sums of powers in Eulerian numbers). For non-negative integers \(r,n,m\) and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{r+1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \tbinom{j-t+n+r}{j+r+1} + \sum_{s=0}^{r} (-1)^{j+s} \tbinom{t}{j+s+1} \tbinom{r-s+n-1}{r-s} \right] \tbinom{t+k-j}{m-j} % {\textstyle\genfrac\langle\rangle{0pt}{}{m}{k}}% . \end{align*}\]
In this manuscript, we derived formulas for multifold sums of
powers [theorem:multifold-sums-of-powers-via-backward-difference],
by utilizing Newton’s interpolation series in backward differences. In
addition, we highlight that backward differences of powers are closely
related to Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\), and
Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{m}{k}\).
Thus, we expressed formulas for multifold sums of powers in terms of
Stirling numbers of the second kind [prop:multifold-sums-of-powers-in-stirling-numbers]
and Eulerian numbers [prop:multifold-sums-of-powers-in-eulerian-numbers].
Future research directions are discussed and proposed in (Kolosov
2025a), which includes development of generalized framework for
sums of powers using interpolation formulas combined with hockey stick
identities for binomial coefficients. All the results are validated
using Mathematica programs; see Section [sec:mathematica-programs].
Use the Mathematica package (Kolosov 2026) to validate the results
| Mathematica Function | Validates / Prints |
|---|---|
MultifoldSumOfPowersRecurrence[r, n, m] |
Computes \(\Sigma^{r}\,{n}^{m}\) |
ValidateOrdinarySumsOfPowersViaBackwardDifferences[20] |
Validates [prop:negated-backward-sums-of-powers] |
ValidateBackwardDifferencesInEulerianNumbers[20] |
Validates [lem:backward-differences-in-eulerian-numbers] |
ValidateOrdinarySumsOfPowersInEulerianNumbers[10] |
Validates [prop:ordinary-sums-of-powers-in-eulerian-numbers] |
ValidateBackwardDifferencesInStirlingNumbers[20] |
Validates [lem:backward-differences-in-stirling-numbers] |
ValidateOrdinarySumsOfPowersInStirlingNumbers[20] |
Validates [prop:ordinary-sums-of-powers-in-stirling-numbers] |
ValidateOrdinaryStirlingSumsOfPowersInZero[20] |
Validates [prop:ordinary-stirling-sums-of-powers-in-zero] |
ValidateOrdinaryStirlingSumsOfPowersInZeroAltered[20] |
Validates [prop:ordinary-stirling-sums-of-powers-in-zero-altered] |
ValidateDoubleSumsOfPowersViaBackwardDifferences[10] |
Validates [prop:double-sums-of-powers-via-backward-differences] |
ValidateMultifoldSumsOfPowersViaBackwardDifference[5] |
Validates [theorem:multifold-sums-of-powers-via-backward-difference] |
ValidateMultifoldSumsOfPowersBackwardDiffBinomialForm[5] |
Validates [prop:multifold-sums-of-powers-via-backward-difference-binomial-form] |
ValidateMultifoldSumsOfPowersBinomialFormShifted[5] |
Validates [cor:multifold-sums-of-powers-via-backward-difference-binomial-form-altered] |
ValidateMultifoldSumsOfPowersInStirlingNumbers[5] |
Validates [prop:multifold-sums-of-powers-in-stirling-numbers] |
ValidateMultifoldSumsOfPowersInEulerianNumbers[5] |
Validates [prop:multifold-sums-of-powers-in-eulerian-numbers] |
Metadata
Initial release date: January 1, 2026.
Current release date: 2026-01-24.
Version:
1.6.1+main.5be10a4
MSC2010: 05A19, 05A10, 11B68, 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