2026-01-05
We obtain 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 obtain formulas for sums of powers via Newton’s interpolation formula based on backward finite differences of powers. The idea to derive sums of powers using difference operator and Newton’s series is quite generic, thus, formulas for sums of powers using forward and central differences can be found in the works (Kolosov 2025a, 2025b).
Define multifold sums of powers in Knuth’s (Knuth, Donald E. 1993) notation \[\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*}\] The book Interpolation by Steffensen (Steffensen, Johan Frederik 1927, chap. 2, eq. (19)) gives Newton’s formula for backward differences evaluated in zero \(f(x) = \sum_{k=0}^{n} \binom{x+k-1}{k} \nabla^{k} f(0)\).
In general,
Proposition 1 (Newton formula via backward differences).
\[\begin{align*} f(x) &= \sum_{k=0}^{n} \binom{x-a+k-1}{k} \nabla^{k} f(a) \end{align*}\] where \(\nabla^{k} f(a) = \sum_{j=0}^{k} (-1)^{j} \binom{k}{j} f(a-j)\).
Thus, by setting \(f(n)=n^m\) \[\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, ordinary sums of powers is equivalent to \[\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{-t+j-1+k}{j} = \sum_{m=j-t}^{j-t-1+n} \binom{m}{j} \end{align*}\] Thus, \[\begin{align*} \sum_{k=1}^{n} \binom{-t+j-1+k}{j} = \binom{j-t+n}{j+1} - \binom{j-t}{j+1} \end{align*}\] Because,
Lemma 2 (Generalized hockey stick identity). \[\begin{align*} \sum_{m=a}^{b} \binom{m}{j} = \binom{b+1}{j+1} - \binom{a}{j+1} \end{align*}\]
Applying the identity for binomial coefficients \(\binom{-k}{j} = (-1)^j \binom{j+k-1}{j}\), we obtain
Proposition 3 (Ordinary sums of powers via backward differences).
For non-negative integers \(n,m\) and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{1}\,{n}^{m} &= \sum_{j=0}^{m} \nabla^{j} t^{m} \left[ (-1)^j \binom{t}{j+1} + \binom{j-t+n}{j+1} \right] \end{align*}\]
For example, by setting \(t=2\) and \(m=1,2,3,4\), we get formulas for sums of cubes \[\begin{align*} \Sigma^{1}\,{n}^{1} &= 2\left[ -\binom{2}{1} + \binom{n-2}{1} \right] + 1\left[ \binom{2}{2} + \binom{n-1}{2} \right], \end{align*}\] \[\begin{align*} \Sigma^{1}\,{n}^{2} &= 4\left[ -\binom{2}{1} + \binom{n-2}{1} \right] + 3\left[ \binom{2}{2} + \binom{n-1}{2} \right] \\ &\quad + 2\left[ -\binom{2}{3} + \binom{n}{3} \right]. \end{align*}\] \[\begin{align*} \Sigma^{1}\,{n}^{3} &= 8\left[ -\binom{2}{1} + \binom{n-2}{1} \right] + 7\left[ \binom{2}{2} + \binom{n-1}{2} \right] \\ &\quad + 6\left[ -\binom{2}{3} + \binom{n}{3} \right] + 6\left[ \binom{2}{4} + \binom{n+1}{4} \right]. \end{align*}\] \[\begin{align*} \Sigma^{1}\,{n}^{4} &= 16\left[ -\binom{2}{1} + \binom{n-2}{1} \right] + 15\left[ \binom{2}{2} + \binom{n-1}{2} \right] \\ &\quad + 14\left[ -\binom{2}{3} + \binom{n}{3} \right] + 12\left[ \binom{2}{4} + \binom{n+1}{4} \right] \\ &\quad + 24\left[ -\binom{2}{5} + \binom{n+2}{5} \right]. \end{align*}\]
For \(t=0\) the coefficients are
\(1, 0, 1, 0, -1, 2, 0, 1, -6,
6,\ldots\) and registered in the OEIS (Sloane, Neil J.A. and others 2003)
as A278075.
For \(t=1\) the coefficients are
\(1, 1, 1, 1, 1, 2, 1, 1, 0, 6,\ldots\)
and registered in the OEIS (Sloane, Neil J.A. and others 2003)
as A389570.
For \(t=2\) the coefficients are
\(1, 2, 1, 4, 3, 2, 8, 7, 6, 6,\ldots\)
and registered in the OEIS (Sloane, Neil J.A. and others 2003)
as A391068.
For \(t=3\) the coefficients are
\(1, 3, 1, 9, 5, 2, 27, 19, 12,
6,\ldots\) and registered in the OEIS (Sloane, Neil J.A. and others 2003)
as A391210.
Lemma 4 (Backward differences in Eulerian numbers). \[\begin{align*} \Delta^{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 binomial recurrence \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\), see (Worpitzky 1883). ◻
Thus, let be a formula for ordinary sums of powers in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{m}{k}\)
Proposition 5 (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*}\]
Remarkable that having \(t=0\) formula for sums of powers turns into double binomial view
Proposition 6 (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 7 (Backward differences in Stirling numbers). \[\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 8 (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 9 (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 \(\binom{-k}{j} = (-1)^j \binom{j+k-1}{j}\) yields another binomial form for sums of powers
Proposition 10 (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*}\]
Formula for double sums of powers can be derived in a similar manner, by applying summation to the proposition [prop:ordinary-sums-of-powers-via-backward-differences], test testsad which in turn implies generalized hockey-stick identity, 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, \[\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 11 (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*}\]
In general,
Theorem 12 (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 13 (Multifold sum of zero powers). For integers \(r\) and \(n\) \[\begin{align*} \Sigma^{r}\,{n}^{0} = \binom{r+n-1}{r} \end{align*}\]
Proof. By hockey stick identity \(\sum_{k=0}^{t} \binom{j+k}{j} = \binom{j+t+1}{j+1}\). ◻
By \(\Sigma^{r-1-s}\,{n}^{0} = \binom{r-s+n-2}{r-s-1}\), we get
Proposition 14 (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\)
Corollary 15 (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
Proposition 16 (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[ \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] \binom{t-j}{k-j} \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
Proposition 17 (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[ \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] \binom{t+k-j}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k} \end{align*}\]
In this manuscript, we derived formula for sums of powers [theorem:multifold-sums-of-powers-via-backward-difference] by utilizing Newton’s interpolation series for backward finite differences of powers. In addition, we noticed that backward differences are closely related to Stirling numbers of the second kind, and Eulerian numbers. Thus, we expressed formulas for 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 at (Kolosov 2025a), which includes development of generalized algorithm for sums of powers using interpolation formulas combined with hockey-stick family 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 Proposition [prop:ordinary-sums-of-powers-via-backward-differences] |
ValidateBackwardDifferencesInEulerianNumbers[20] |
Validates Lemma [lem:backward-differences-in-eulerian-numbers] |
ValidateOrdinarySumsOfPowersInEulerianNumbers[10] |
Validates Proposition [prop:ordinary-sums-of-powers-in-eulerian-numbers] |
ValidateBackwardDifferencesInStirlingNumbers[20] |
Validates Lemma [lem:backward-differences-in-stirling-numbers] |
ValidateOrdinarySumsOfPowersInStirlingNumbers[20] |
Validates Proposition [prop:ordinary-sums-of-powers-in-stirling-numbers] |
ValidateOrdinaryStirlingSumsOfPowersInZero[20] |
Validates Proposition [prop:ordinary-stirling-sums-of-powers-in-zero] |
ValidateOrdinaryStirlingSumsOfPowersInZeroAltered[20] |
Validates Proposition [prop:ordinary-stirling-sums-of-powers-in-zero-altered] |
ValidateDoubleSumsOfPowersViaBackwardDifferences[10] |
Validates Proposition [prop:double-sums-of-powers-via-backward-differences] |
ValidateMultifoldSumsOfPowersViaBackwardDifference[5] |
Validates Theorem [theorem:multifold-sums-of-powers-via-backward-difference] |
ValidateMultifoldSumsOfPowersBackwardDiffBinomialForm[5] |
Validates Proposition [prop:multifold-sums-of-powers-via-backward-difference-binomial-form] |
ValidateMultifoldSumsOfPowersBinomialFormShifted[5] |
Validates Proposition [cor:multifold-sums-of-powers-via-backward-difference-binomial-form-altered] |
ValidateMultifoldSumsOfPowersInStirlingNumbers[5] |
Validates Proposition [prop:multifold-sums-of-powers-in-stirling-numbers] |
ValidateMultifoldSumsOfPowersInEulerianNumbers[5] |
Validates Proposition [prop:multifold-sums-of-powers-in-eulerian-numbers] |
Version: Local-0.1.0
License: This work is licensed under a CC BY 4.0 License.
Sources: github.com/kolosovpetro/SumsOfPowersViaBackwardDifferences
ORCID: 0000-0002-6544-8880
DOI: 10.5281/zenodo.18118011
Email: kolosovp94@gmail.com