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

Abstract

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

Definition 3 (Central factorials). For integers \(n,k\) \[\begin{align*} n^{[k]} = \begin{cases} 0, \quad & \mathrm{if \; } k < 0, \\ 1, \quad & \mathrm{if \; } k = 0, \\ n \left( n + \frac{k}{2} -1 \right)\left( n + \frac{k}{2} -2 \right) \cdots \left( n - \frac{k}{2} +1 \right) = n \left(n+\frac{k}{2}-1\right)_{k-1}, \quad & \mathrm{if \; } k>0, \end{cases} \end{align*}\] where \(\left(n+\frac{k}{2}-1\right)_{k-1} = \prod_{j=0}^{k-2} \left( n+\frac{k}{2}-1 -j \right)\) are falling factorials.

We encourage the audience to read J. F. Steffensen’s work on the definition of generalized factorials (Steffensen 1933).

Lemma 4 (Central Newton’s formula). For a function \(f\) defined on integers and arbitrary integers \(x,t\) \[\begin{align*} f(x) = \sum_{k=0}^{\infty} \frac{(x-t)^{[k]}}{k!} \delta^{k} f(t), \end{align*}\] where \(\delta^{k} f(t)\) denotes the \(k\)-th central finite difference \[\begin{align*} \delta^{k} f(t) = \mathop{\textstyle\sum}_{j=0}^{k} (-1)^j \tbinom{k}{j} f\!\left(t+\tfrac{k}{2} - j\right), \end{align*}\] and \((x-t)^{[k]}\) are central factorials defined by [def:central-factorials].

Proof. See (Butzer et al. 1989, 462), and (Steffensen, Johan Frederik 1927, sec. 2, eq. (19)), and (Riordan 1968, sec. 6, eq. (21)). ◻

Lemma 5 (Newton’s formula for powers). For non-negative integers \(n,m\), and an arbitrary integer \(t\), \[\begin{align*} n^m = \sum_{k=0}^{m} \frac{(n-t)^{[k]}}{k!} \delta^{k} t^m. \end{align*}\]

Proof. Special case of Lemma [lem:central-newtons-formula] for \(f(n) = n^m\). ◻

Lemma 6 (Central factorials binomial form). For integers \(n\) and \(k\neq0\), \[\begin{align*} \frac{n^{[k]}}{k!} = \frac{n}{k} \binom{n+\frac{k}{2}-1}{k-1}. \end{align*}\]

Proof. We have \[\begin{align*} \frac{n^{[k]}}{k!} &= \frac{n}{k!}\left(n+\frac{k}{2}-1\right)_{k-1} = \frac{n}{k (k-1)!} \left(n+\frac{k}{2}-1\right)_{k-1} = \frac{n}{k} \binom{n+\frac{k}{2}-1}{k-1}, \end{align*}\] because of the identity in falling factorials \(\frac{\left(x\right)_{n}}{n!} = \binom{x}{n}\). ◻

Lemma 7 (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 8 (Centered hockey-stick identity). For integer \(n\geq1\), and arbitrary integers \(t,k,r\) \[\begin{align*} \sum_{j=1}^{n} \binom{j -t + \frac{k}{2} +r}{k} = \binom{n -t + \frac{k}{2} + r +1}{k+1} - \binom{1 -t + \tfrac{k}{2} +r}{k+1}. \end{align*}\]

Proof. By setting \(a=1 -t + \tfrac{k}{2} +r\), and \(b=n-t+ \tfrac{k}{2} +r\) into Lemma [lem:generalized-hockey-stick-identity] yields \[\begin{align*} \mathop{\textstyle\sum}_{j=1}^{n} \tbinom{j -t + \tfrac{k}{2} +r}{k} = \mathop{\textstyle\sum}_{j=1 -t + \tfrac{k}{2} +r}^{n -t + \tfrac{k}{2} +r} \tbinom{j}{k} = \tbinom{n -t + \tfrac{k}{2} + r +1}{k+1} - \tbinom{1 -t + \tfrac{k}{2} +r}{k+1}. \end{align*}\] This completes the proof. ◻

Lemma 9 (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.

Let \(r=0\), then we have \(\Sigma^{0}\,{n}^{0} = 1\), by definition [def:multifold-sums-of-powers-recurrence].
Let \(r=1\), then we have \(\Sigma^{1}\,{n}^{0} = \sum_{k=1}^{n} 1 = \binom{n}{1}\).
Let \(r=2\), then we have \(\Sigma^{2}\,{n}^{0} = \sum_{k=1}^{n} \binom{k}{1} = \binom{n+1}{2}\).
Let \(r=3\), then we have \(\Sigma^{3}\,{n}^{0} = \sum_{k=1}^{n} \binom{k+1}{2} = \binom{n+2}{3}\).
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. ◻

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 central Newton’s interpolation formula for powers [lem:central-newtons-formula-for-powers] with hockey-stick identity [lem:centered-hockey-stick-identity]. We implement the algorithm for finding closed forms of sums of powers of integers, proposed in (Kolosov 2026a, 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 central Newton’s formula, and hockey-stick identity [lem:centered-hockey-stick-identity].

Main results

We start our discussion from Lemma [lem:central-newtons-formula-for-powers], which yields backward Newton’s interpolation formula for powers. Therefore, by applying Lemma [lem:central-factorials-binomial-form] to Newton’s interpolation formula [lem:central-newtons-formula-for-powers], for non-negative integers \(n,m\) and an arbitrary integer \(t\) yields \[\begin{align*} n^m &= \frac{(n-t)^{[0]}}{0!} \delta^{0} t^m + \sum_{k=1}^{m} \frac{n-t}{k} \binom{n+t+\frac{k}{2}-1}{k-1} \delta^{k} t^m \\ &= t^m + \sum_{k=1}^{m} (n-t) \binom{n-t+\frac{k}{2}-1}{k-1} \frac{\delta^{k} t^m}{k}. \end{align*}\] Note that we isolate the term \(\frac{(n-t)^{[0]}}{0!} \delta^{0} t^m\) to avoid division by zero. By expanding the brackets, we have \[\begin{align*} n^m = t^m + \sum_{k=1}^{m} \frac{\delta^{k} t^m}{k} \left[ n\binom{n-t+\frac{k}{2}-1}{k-1} - t\binom{n-t+\frac{k}{2}-1}{k-1} \right]. \end{align*}\] Now we notice that sum above has an additional factor \(n\) in its binomial basis \(n\binom{n-t+\frac{k}{2}-1}{k-1}\), preventing us from using centered hockey-stick identity [lem:centered-hockey-stick-identity] for closed form. Thus, consider the following Lemma

Lemma 11 (Binomial decomposition). For non-negative integers \(r,n,m\) \[\begin{align*} n \binom{n+r}{m} = (m+1) \binom{n+r}{m+1} - (r-m) \binom{n+r}{m}. \end{align*}\]

Proof. By expanding the brackets yields, \[\begin{align*} n \binom{n+r}{m} = m \binom{n+r}{m+1} + \binom{n+r}{m+1} - r \binom{n+r}{m} + m \binom{n+r}{m}. \end{align*}\] Recall the extraction property of binomial coefficients \(\binom{n}{k+1} = \frac{n-k}{k+1} \binom{n}{k}\). Therefore, by extraction property \[\begin{align*} \binom{n+r}{m+1} = \frac{n+r-m}{m+1} \binom{n+r}{m}. \end{align*}\] Thus, \[\begin{align*} n \binom{n+r}{m} &= m \frac{n+r-m}{m+1} \binom{n+r}{m} + \frac{n+r-m}{m+1} \binom{n+r}{m} - r \binom{n+r}{m} + m \binom{n+r}{m}. \end{align*}\] By factoring out binomial coefficient \(\binom{n+r}{m}\) yields \[\begin{align*} n \binom{n+r}{m} &= \binom{n+r}{m} \left[ m \frac{n+r-m}{m+1} + \frac{n+r-m}{m+1} - r + m \right] \\ &= \binom{n+r}{m} \left[ (m+1) \frac{n+r-m}{m+1} - r + m \right] \\ &= \binom{n+r}{m}n. \end{align*}\] This completes the proof. ◻

Hence, by setting \(r \rightarrow -t+\frac{k}{2} -1\), and \(m \rightarrow k-1\) into Lemma [lem:binomial-decomposition] gives \[\begin{align*} n \binom{n-t+\frac{k}{2} -1}{k-1} = k \binom{n-t+\frac{k}{2}-1}{k} + \left [t+\frac{k}{2} \right ] \binom{n-t+\frac{k}{2}-1}{k-1}. \end{align*}\] Because, by binomial decomposition [lem:binomial-decomposition], we have \[\begin{align*} n \tbinom{n-t+\frac{k}{2} -1}{k-1} &= k \tbinom{n-t+\frac{k}{2} -1}{k-1+1} - \left [-t+\tfrac{k}{2} -1-(k-1)\right ] \tbinom{n-t+\frac{k}{2} -1}{k-1} \\ &= k \tbinom{n-t+\frac{k}{2}-1}{k} - \left [-t-\tfrac{k}{2} \right ] \tbinom{n-t+\tfrac{k}{2}-1}{k-1} \\ &= k \tbinom{n-t+\tfrac{k}{2}-1}{k} + \left [t+\tfrac{k}{2} \right ] \tbinom{n-t+\tfrac{k}{2}-1}{k-1}. \end{align*}\] Thus, \[\begin{align*} n^m = t^m + \sum_{k=1}^{m} \frac{\delta^{k} t^m}{k} \left[ k \binom{n-t+\frac{k}{2}-1}{k} + \left[t+\frac{k}{2} \right] \binom{n-t+\frac{k}{2}-1}{k-1} - t \binom{n-t+\frac{k}{2}-1}{k-1} \right]. \end{align*}\] By collapsing the terms \(t \binom{n-t+\frac{k}{2}-1}{k-1}\), and by simplifying the factors \(k\) yields \[\begin{align*} n^m = t^m + \sum_{k=1}^{m} \left[ \binom{n-t+\frac{k}{2}-1}{k} + \frac{1}{2} \binom{n-t+\frac{k}{2}-1}{k-1} \right] \delta^{k} t^m. \end{align*}\] We move the term \(t^m\) under the summation, thus \[\begin{align*} n^m = \sum_{k=0}^{m} \left[ \binom{n-t+\frac{k}{2}-1}{k} + \frac{1}{2} \binom{n-t+\frac{k}{2}-1}{k-1} \right] \delta^{k} t^m. \end{align*}\] Now, we simplify the binomial basis \(\binom{n-t+\frac{k}{2}-1}{k}+\frac{1}{2}\binom{n-t+\frac{k}{2}-1}{k-1}\) to get rid of fractions inside of it. Let \(a=n-t+\frac{k}{2}-1\), then \[\begin{align*} \binom{a}{k} + \frac{1}{2} \binom{a}{k-1} = \frac{1}{2} \left[ 2 \binom{a}{k} + \binom{a}{k-1} \right] = \frac{1}{2} \left[ \binom{a}{k} + \binom{a+1}{k} \right]. \end{align*}\] Therefore, \[\begin{align*} n^m = \frac{1}{2} \sum_{k=0}^{m} \left[ \binom{n-t+\frac{k}{2}-1}{k} + \binom{n-t+\frac{k}{2}}{k-1} \right] \delta^{k} t^m. \end{align*}\] Note that we do not bother ourselves about fractions in upper index of binomial coefficients \(\binom{n-t+\frac{k}{2}-1}{k}\), and \(\binom{n-t+\frac{k}{2}}{k-1}\), because binomial coefficient \(\binom{n}{k}\) is a polynomial in \(n\). The well-known identity in unsigned Stirling numbers of the first kind \(\genfrac{[}{]}{0pt}{}{n}{k}\) shows it explicitly \[\begin{align*} \binom{n}{k} = \sum_{j=0}^{k} \frac{(-1)^{k-j}}{k!} \genfrac{[}{]}{0pt}{}{k}{j} n^j. \end{align*}\] For example,

Example 12. For integer \(0 \le t \le 3\), we have \[\begin{align*} t=0:\quad n^3 &= \bigl(1+\tbinom{n}{-1}\bigr)\cdot0 +\tfrac{1}{2}(1+2n)\cdot\tfrac{1}{4} +\tfrac{1}{2}(2+n+n^2)\cdot0 \\ &+\tfrac{1}{48}(21+46n+12n^2+8n^3)\cdot6, \\ t=1:\quad n^3 &= \bigl(1+\tbinom{n-1}{-1}\bigr)\cdot1 +\tfrac{1}{2}(-1+2n)\cdot\tfrac{13}{4} +\tfrac{1}{2}(2-n+n^2)\cdot6 \\ &+\tfrac{1}{48}(-21+46n-12n^2+8n^3)\cdot6, \\ t=2:\quad n^3 &= \bigl(1+\tbinom{n-2}{-1}\bigr)\cdot8 +\tfrac{1}{2}(-3+2n)\cdot\tfrac{49}{4} +\tfrac{1}{2}(4-3n+n^2)\cdot12 \\ &+\tfrac{1}{48}(-87+94n-36n^2+8n^3)\cdot6, \\ t=3:\quad n^3 &= \bigl(1+\tbinom{n-3}{-1}\bigr)\cdot27 +\tfrac{1}{2}(-5+2n)\cdot\tfrac{109}{4} +\tfrac{1}{2}(8-5n+n^2)\cdot18 \\ &+\tfrac{1}{48}(-225+190n-60n^2+8n^3)\cdot6. \end{align*}\]

Hence, we can utilize centered hockey-stick identity [lem:centered-hockey-stick-identity] for closed formula for sums of powers, because \[\begin{align*} \Sigma^{1}\,{n}^{m} = \frac{1}{2} \sum_{k=0}^{m} \left[ \sum_{j=1}^{n} \binom{j-t+\frac{k}{2}-1}{k} + \sum_{j=1}^{n} \binom{j-t+\frac{k}{2}}{k-1} \right] \delta^{k} t^m. \end{align*}\] Therefore, by Lemma [lem:centered-hockey-stick-identity] \[\begin{align*} \begin{cases} \sum_{j=1}^{n} \binom{j-t+\frac{k}{2}-1}{k} &= \binom{n -t + \frac{k}{2} +0}{k+1} - \binom{0 -t + \tfrac{k}{2}}{k+1}, \\ \sum_{j=1}^{n} \binom{j-t+\frac{k}{2}}{k-1} &= \binom{n -t + \frac{k}{2} +1}{k+1} - \binom{1 -t + \tfrac{k}{2}}{k+1}. \end{cases} \end{align*}\] Thus, closed formula for ordinary sums of powers follows

Proposition 13 (Ordinary sums of powers). For non-negative integers \(n,m\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{1}\,{n}^{m} = \frac{1}{2} \sum_{k=0}^{m} \left[ \binom{n -t + \frac{k}{2} +0}{k+1} + \binom{n -t + \frac{k}{2} +1}{k+1} - \binom{0 -t + \tfrac{k}{2}}{k+1} - \binom{1 -t + \tfrac{k}{2}}{k+1} \right] \delta^{k} t^m. \end{align*}\]

Example 14. For integer \(0 \leq t \leq 4\), we have \[\begin{align*} t=0:\quad \Sigma^{1}\,{n}^{3} &= 2n\cdot0 +(n+n^2)\cdot\tfrac{1}{4} +\tfrac{1}{6}(n+3n^2+2n^3)\cdot0 \\ &+\tfrac{1}{24}(-n+n^2+4n^3+2n^4)\cdot6, \\ t=1:\quad \Sigma^{1}\,{n}^{3} &= 2n\cdot1 +(-n+n^2)\cdot\tfrac{13}{4} +\tfrac{1}{6}(n-3n^2+2n^3)\cdot6 \\ &+\tfrac{1}{24}(n+n^2-4n^3+2n^4)\cdot6, \\ t=2:\quad \Sigma^{1}\,{n}^{3} &= 2n\cdot8 +(-3n+n^2)\cdot\tfrac{49}{4} +\tfrac{1}{6}(13n-9n^2+2n^3)\cdot12 \\ &+\tfrac{1}{24}(-21n+25n^2-12n^3+2n^4)\cdot6, \\ t=3:\quad \Sigma^{1}\,{n}^{3} &= 2n\cdot27 +(-5n+n^2)\cdot\tfrac{109}{4} +\tfrac{1}{6}(37n-15n^2+2n^3)\cdot18 \\ &+\tfrac{1}{24}(-115n+73n^2-20n^3+2n^4)\cdot6, \\ t=4:\quad \Sigma^{1}\,{n}^{3} &= 2n\cdot64 +(-7n+n^2)\cdot\tfrac{193}{4} +\tfrac{1}{6}(73n-21n^2+2n^3)\cdot24 \\ &+\tfrac{1}{24}(-329n+145n^2-28n^3+2n^4)\cdot6. \end{align*}\]

Similarly, by setting \(r=0\), and \(r=1\) into Lemma [lem:centered-hockey-stick-identity], we have \[\begin{align*} \begin{cases} \sum_{j=1}^{n} \binom{j -t + \frac{k}{2} +0}{k+1} &= \binom{n -t + \frac{k}{2} +1}{k+2} - \binom{1 -t + \tfrac{k}{2}}{k+2}, \\ \sum_{j=1}^{n} \binom{j -t + \frac{k}{2} +1}{k+1} &= \binom{n -t + \frac{k}{2} + 2}{k+2} - \binom{2 -t + \tfrac{k}{2}}{k+2}. \end{cases} \end{align*}\] Hence,

Proposition 15 (Double sums of powers). For non-negative integers \(n,m\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{2}\,{n}^{m} &= \frac{1}{2} \sum_{k=0}^{m} \Bigg[ \binom{n -t + \frac{k}{2} +1}{k+2} +\binom{n -t + \frac{k}{2} + 2}{k+2} \\ &- \Bigg( \binom{0 -t + \tfrac{k}{2}}{k+1} +\binom{1 -t + \tfrac{k}{2}}{k+1} \Bigg) \Sigma^{1}\,{n}^{0} \\ &- \Bigg( \binom{1 -t + \tfrac{k}{2}}{k+2} +\binom{2 -t + \tfrac{k}{2}}{k+2} \Bigg) \Sigma^{0}\,{n}^{0} \Bigg] \delta^{k} t^m. \end{align*}\]

Example 16. For integer \(0 \le t \le 2\), we have \[\begin{align*} t=0:\quad \Sigma^{1}\,{n}^{3} &= \tfrac{1}{2}(n+n^2)\cdot0 +\tfrac{1}{48}(-3-2n+12n^2+8n^3)\cdot\tfrac{1}{4} \\ &+\tfrac{1}{24}(-2n-n^2+2n^3+n^4)\cdot0 \\ &+\tfrac{1}{3840}(45+18n-200n^2-80n^3+80n^4+32n^5)\cdot6, \\ t=1:\quad \Sigma^{1}\,{n}^{3} &= \tfrac{1}{2}(-n+n^2)\cdot1 +\tfrac{1}{48}(3-2n-12n^2+8n^3)\cdot\tfrac{13}{4} \\ &+\tfrac{1}{24}(2n-n^2-2n^3+n^4)\cdot6 \\ &+\tfrac{1}{3840}(-45+18n+200n^2-80n^3-80n^4+32n^5)\cdot6, \\ t=2:\quad \Sigma^{1}\,{n}^{3} &= \tfrac{1}{2}(2-3n+n^2)\cdot8 +\tfrac{1}{48}(-15+46n-36n^2+8n^3)\cdot\tfrac{49}{4} \\ &+\tfrac{1}{24}(-6n+11n^2-6n^3+n^4)\cdot12 \\ &+\tfrac{1}{3840}(105-142n-360n^2+560n^3-240n^4+32n^5)\cdot6. \end{align*}\]

Theorem 17 (Multifold sums of powers). For non-negative integers \(r,n,m\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{r}\,{n}^{m} &= \frac{1}{2} \sum_{k=0}^{m} \Bigg[ \binom{n-t+\frac{k}{2}+r-1}{k+r} + \binom{n-t+\frac{k}{2}+r}{k+r} \\ &- \sum_{s=0}^{r-1} \Bigg( \binom{s-t+\frac{k}{2}}{k+s+1} + \binom{s-t+\frac{k}{2}+1}{k+s+1} \Bigg) \Sigma^{r-1-s}\,{n}^{0} \Bigg] \delta^{k} t^{m}. \end{align*}\]

Proposition 18 (Multifold Binomial sums of powers). For non-negative integers \(r,n,m\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{r}\,{n}^{m} &= \frac{1}{2} \sum_{k=0}^{m} \Bigg[ \binom{n-t+\frac{k}{2}+r-1}{k+r} + \binom{n-t+\frac{k}{2}+r}{k+r} \\ &- \sum_{s=0}^{r-1} \Bigg( \binom{s-t+\frac{k}{2}}{k+s+1} + \binom{s-t+\frac{k}{2}+1}{k+s+1} \Bigg) \binom{r-s+n-2}{r-s-1} \Bigg] \delta^{k} t^{m}. \end{align*}\]

Therefore, we have successfully derived multifold formulas for sums of powers, in closed form. The work (Kolosov 2025) provides implementation of algorithm proposed in (Kolosov 2026a, Alg. (11.2)), in terms of forward finite differences \(\Delta\), and Newton’s formula. Similarly, the work (Kolosov 2026b) discusses multifold formulas for sums of powers in terms of backward differences \(\nabla\), and Newton’s formula.

Remark on Knuth’s formula

In (Knuth, Donald E. 1993) Donald Knuth provides a remarkable formula for sums of odd powers, in terms of central factorial numbers of the second kind \(T(n,k)\)

See the sequence A008957 in the OEIS (Sloane, Neil J.A. and others 2003) for central factorial numbers of the second kind. It is quite interesting to notice that Proposition [prop:knuth-odd-powers-sum] originates from centered Newton’s formula for powers [lem:central-newtons-formula-for-powers] evaluated at zero. By central Newton’s formula, for \(m\geq 1\), we have \[\begin{align*} n^{2m} = \sum_{k=1}^{2m} \frac{n^{[k]}}{k!} \cdot \delta^{k} 0^{2m} \end{align*}\] The iteration for \(k=0\) can be omitted because \(\delta^{0} 0^{2m} = 0\). Now, we observe that central difference \(\delta^k 0^m\) satisfies the parity of arguments \(m\) and \(k\), such that \[\begin{align*} \begin{cases} \delta^{k} 0^m \neq 0, \quad &\text{when} \quad m \equiv k \pmod{2}, \\ \delta^{k} 0^m = 0, \quad &\text{when} \quad m \not\equiv k \pmod{2}, \end{cases} \end{align*}\] meaning that \(\delta^{k} 0^m\) is zero whether \(k,m\) are odd and even, and vise versa. Note that the parity property holds only for central difference of powers evaluated at zero, by contrast \(\delta^{3} 1^{4} = 24 \neq 0\). Thus, the parity of \(\delta^{k} 0^{2m}\) allows us to omit odd iterations of \(k\), because \(\delta^{k} 0^{2m}\) is zero for odd \(k\) \[\begin{align*} n^{2m} = \sum_{k=1}^{m} \frac{n^{[2k]}}{(2k)!} \cdot \delta^{2k} 0^{2m}. \end{align*}\] By definition of central factorial numbers of the second kind, yields \[\begin{align*} n^{2m} = \sum_{k=1}^{m} n^{[2k]} T(2m,2k). \end{align*}\] Thus, \[\begin{align*} n^{2m} = \sum_{k=1}^{m} (2k)! \frac{n^{[2k]}}{(2k)!} T(2m,2k) \end{align*}\] By simplifying \(\frac{n^{[2k]}}{(2k)!}\) using Lemma [lem:central-factorials-binomial-form], we get \[\begin{align*} n^{2m} = \sum_{k=1}^{m} (2k)! \frac{n}{2k} \binom{n+k-1}{2k-1} T(2m,2k). \end{align*}\] Therefore, \[\begin{align*} n^{2m} = \sum_{k=1}^{m} (2k-1)! n \binom{n+k-1}{2k-1} T(2m,2k). \end{align*}\] By factoring out \(n\), we obtain \[\begin{align*} n^{2m-1} &= \sum_{k=1}^{m} (2k-1)! \binom{n+k-1}{2k-1} T(2m,2k). \end{align*}\] By using hockey-stick identity \(\sum_{k=0}^{n} \binom{k}{j} = \binom{n+1}{j+1}\) yields \[\begin{align*} \Sigma^{1}\,{n}^{2m-1} = \sum_{k=1}^{m} (2k-1)! \binom{n+k}{2k} T(2m,2k). \end{align*}\] The formula above matches the Proposition [prop:knuth-odd-powers-sum] precisely. Clearly, the formula for sums of odd powers can be generalized to multifold case, by applying hockey-stick identity \(\sum_{k=0}^{n} \binom{k}{j} = \binom{n+1}{j+1}\) repeatedly

Example 21. For non-negative integers \(n\), and \(r=1\), we have \[\begin{align*} \Sigma^{1}\,{n}^{1} &= \tbinom{n+1}{2} 1, \\ \Sigma^{1}\,{n}^{3} &= \tbinom{n+2}{4} 6 + \tbinom{n+1}{2} 1, \\ \Sigma^{1}\,{n}^{5} &= \tbinom{n+3}{6} 120 + \tbinom{n+2}{4} 30 + \tbinom{n+1}{2} 1, \\ \Sigma^{1}\,{n}^{7} &= \tbinom{n+4}{8} 5040 + \tbinom{n+3}{6} 1680 + \tbinom{n+2}{4} 126 + \tbinom{n+1}{2} 1. \end{align*}\]

Example 22. For non-negative integers \(r,n\) \[\begin{align*} \Sigma^{r}\,{n}^{1} &= \tbinom{n+0+r}{1+r} 1, \\ \Sigma^{r}\,{n}^{3} &= \tbinom{n+1+r}{3+r} 6 + \tbinom{n+0+r}{1+r} 1, \\ \Sigma^{r}\,{n}^{5} &= \tbinom{n+2+r}{5+r} 120 + \tbinom{n+1+r}{3+r} 30 + \tbinom{n+0+r}{1+r} 1, \\ \Sigma^{r}\,{n}^{7} &= \tbinom{n+3+r}{7+r} 5040 + \tbinom{n+3+r}{5+r} 1680 + \tbinom{n+1+r}{3+r} 126 + \tbinom{n+0+r}{1+r} 1. \end{align*}\]

The coefficients \(1, 6, 1, 120, 30, 1, 5040, 1680,\ldots\) is the sequence A303675 in the OEIS (Sloane, Neil J.A. and others 2003). However, Proposition [prop:knuth-odd-powers-sum-multifold] serves as the source of inspiration for one more remarkable identity. By Newton’s formula [lem:central-newtons-formula-for-powers], and by Lemma [lem:central-factorials-binomial-form], we have \[\begin{align*} n^m = \sum_{k=1}^{m} \frac{n}{k} \binom{n+\frac{k}{2}-1}{k-1} \delta^{k} 0^m \end{align*}\] By factoring out \(n\) \[\begin{align*} n^{m-1} = \sum_{k=1}^{m} \frac{1}{k} \binom{n+\frac{k}{2}-1}{k-1} \delta^{k} 0^m \end{align*}\] By shifting \[\begin{align*} n^{m} = \sum_{k=1}^{m+1} \frac{1}{k} \binom{n+\frac{k}{2}-1}{k-1} \delta^{k} 0^{m+1} \end{align*}\] By re-indexing \[\begin{align} \label{eq:power-identity-at-zero} n^{m} = \sum_{k=0}^{m} \frac{1}{k+1} \binom{n+\frac{k}{2}-\frac{1}{2}}{k} \delta^{k+1} 0^{m+1} \end{align}\] Thus, by setting \(r=0\) and \(t=\frac{1}{2}\) into Lemma [lem:centered-hockey-stick-identity] yields

Which can also be rewritten in terms of central factorial numbers of the second kind \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{k=0}^{m} k! \left[ \binom{n+\frac{k}{2}+\frac{1}{2}}{k+1} - \binom{\frac{k}{2}+\frac{1}{2}}{k+1}\right] T(k+1, m+1). \end{align*}\] By setting \(r=1\) and \(t=\frac{1}{2}\) into Lemma [lem:centered-hockey-stick-identity], we get formula for double sums of powers

Proposition 24 (Double sums of powers at zero). For non-negative integers \(n,m\) \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{k=0}^{m} \frac{1}{k+1} \left[ \binom{n+\frac{k}{2}+\frac{3}{2}}{k+2} - \binom{\frac{k}{2}+\frac{1}{2}}{k+1} \Sigma^{1}\,{n}^{0} - \binom{\frac{k}{2}+\frac{3}{2}}{k+2} \Sigma^{0}\,{n}^{0} \right] \delta^{k+1} 0^{m+1}. \end{align*}\]

Theorem 25 (Multifold sums of powers at zero). For non-negative integers \(r,n,m\) \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n+\frac{k}{2}+\frac{2r-1}{2}}{k+r} - \sum_{s=0}^{r-1} \binom{\frac{k}{2} + \frac{2(r-s)-1}{2}}{k+r-s} \Sigma^{s}\,{n}^{0} \right] \frac{\delta^{k+1} 0^{m+1}}{k+1}. \end{align*}\]

Proof. By repeatedly applied Lemma [lem:centered-hockey-stick-identity], and Equation [eq:power-identity-at-zero]. ◻

Proposition 26 (Multifold sums of powers at zero binomial form). For non-negative integers \(r,n,m\) \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n+\frac{k}{2}+\frac{2r-1}{2}}{k+r} - \sum_{s=0}^{r-1} \binom{\frac{k}{2} + \frac{2(r-s)-1}{2}}{k+r-s} \binom{s+n-1}{s} \right] \frac{\delta^{k+1} 0^{m+1}}{k+1}. \end{align*}\]

Proof. By repeatedly applied Lemma [lem:centered-hockey-stick-identity], and Equation [eq:power-identity-at-zero]. ◻

Which, as well, can be expressed in terms of central factorial numbers of the second kind \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n+\frac{k}{2}+\frac{2r-1}{2}}{k+r} - \sum_{s=0}^{r-1} \binom{\frac{k}{2} + \frac{2(r-s)-1}{2}}{k+r-s} \binom{s+n-1}{s} \right] k! T(k+1, m+1). \end{align*}\] Thus, we have discussed quite remarkable results, that follow from centered Newton’s formula evaluated at zero.

Conclusions

In this manuscript, we derive closed formulas for multifold sums of powers of integers by combining the central 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
`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]
`ValidateOrdinarySumsOfPowersAtZero.txt`	Validates Prop. [prop:ordinary-sums-of-powers-at-zero]
`ValidateDoubleSumsOfPowersAtZero.txt`	Validates Prop. [prop:double-sums-of-powers-at-zero]
`ValidateMultifoldSumsOfPowersAtZero.txt`	Validates Thm. [thm:multifold-sums-of-powers-at-zero]
`ValidateMultifoldSumsOfPowersAtZeroBinomialForm.txt`	Validates Thm. [prop:multifold-sums-of-powers-at-zero-binomial-form]

Butzer, Paul Leo, K. Schmidt, E. L. Stark, and L. Vogt. 1989. “Central Factorial Numbers; Their Main Properties and Some Applications.” Numerical Functional Analysis and Optimization 10 (5-6): 419–88. https://doi.org/10.1080/01630568908816313.

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. 2025. Newton’s interpolation formula and sums of powers. Zenodo. https://doi.org/10.5281/zenodo.18040979.

Kolosov, Petro. 2026a. Sums of Powers of Integers: A Complete Framework for Closed Formulas. Zenodo. https://doi.org/10.5281/zenodo.20548019.

Kolosov, Petro. 2026b. Sums of powers via backward finite differences and Newton’s formula. Zenodo. https://doi.org/10.5281/zenodo.18118011.

Riordan, John. 1968. Combinatorial Identities. Vol. 217. Https://www.amazon.com/-/de/Combinatorial-Identities-Probability-Mathematical-Statistics/dp/0471722758; Wiley New York.

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.

Auxiliary lemmas

Introduction

Main results

Remark on Knuth’s formula

Conclusions

Mathematica programs