Sums of Powers via Central Finite Differences and Newton’s Formula

Petro Kolosov

2026-11-05

Abstract

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 provide Wolfram Mathematica programs for the efficient verification of the derived identities.

Auxiliary Lemmas

This section introduces the lemmas, definitions, and conventions used in the main results. We use Donald Knuth’s notation for multifold sums of powers as given in (Knuth 1993) because it is concise.

Definition 1 (Multifold sums of powers). For non-negative integers \(r\), \(n\), and \(m\), define the multifold sums of powers recursively 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 define the falling factorial notation as follows.

Definition 2 (Falling factorials). For integers \(n\) and \(k\), define the falling factorial by \[\begin{align*} \left(n\right)_{k} = \begin{cases} 1, & \mathrm{if \; } k = 0, \\ n(n-1)(n-2)\cdots(n-k+1) = \prod_{j=0}^{k-1} (n-j), & \mathrm{if \; } k > 0, \\ 0, & \mathrm{otherwise}. \end{cases} \end{align*}\]

We define the central factorial notation as follows.

Definition 3 (Central factorials). For integers \(n\) and \(k\), define the central factorial by \[\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)\) is a falling factorial.

For further discussion of generalized factorials, see J. F. Steffensen’s treatment in (Steffensen 1933).

Lemma 4 (Central Newton’s formula). Let \(f\) be a function defined on the integers, and let \(x\) and \(t\) be arbitrary integers. \[\begin{align*} f(x) = \sum_{k=0}^{\infty} \frac{(x-t)^{[k]}}{k!} \delta^{k} f(t). \end{align*}\] The \(k\)th central finite difference is defined by \[\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]}\) denotes the central factorial defined in Definition [def:central-factorials].

Proof. Proofs of the central Newton formula are given in (Butzer et al. 1989, 462), in (Steffensen 1927, sec. 2, Equation (19)), and in (Riordan 1968, sec. 6, Equation (21)). ◻

The specialization to powers gives the following lemma.

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

Proof. This is the special case of Lemma [lem:central-newtons-formula] with \(f(n) = n^m\). ◻

The central factorial identity has the following binomial form.

Lemma 6 (Central factorials binomial form). For integers \(n\) and nonzero \(k\), \[\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} \tbinom{n+\frac{k}{2}-1}{k-1}, \end{align*}\] by the falling-factorial identity \(\frac{\left(x\right)_{n}}{n!} = \tbinom{x}{n}\). ◻

The following identity separates a factor of \(n\) from a binomial coefficient.

Lemma 7 (Binomial decomposition). Let \(r\), \(n\), and \(m\) be nonnegative integers. \[\begin{align*} n \binom{n+r}{m} = (m+1) \binom{n+r}{m+1} - (r-m) \binom{n+r}{m}. \end{align*}\]

Proof. Expanding the right-hand side gives \[\begin{align*} n \tbinom{n+r}{m} = m \tbinom{n+r}{m+1} + \tbinom{n+r}{m+1} - r \tbinom{n+r}{m} + m \tbinom{n+r}{m}. \end{align*}\] Recall the extraction property of binomial coefficients \(\tbinom{n}{k+1} = \frac{n-k}{k+1} \tbinom{n}{k}\). The extraction property then gives \[\begin{align*} \tbinom{n+r}{m+1} = \frac{n+r-m}{m+1} \tbinom{n+r}{m}. \end{align*}\] Thus, \[\begin{align*} n \tbinom{n+r}{m} &= m \frac{n+r-m}{m+1} \tbinom{n+r}{m} + \frac{n+r-m}{m+1} \tbinom{n+r}{m} - r \tbinom{n+r}{m} + m \tbinom{n+r}{m}. \end{align*}\] Factoring out the binomial coefficient \(\tbinom{n+r}{m}\) gives \[\begin{align*} n \tbinom{n+r}{m} &= \tbinom{n+r}{m} \left[ m \frac{n+r-m}{m+1} + \frac{n+r-m}{m+1} - r + m \right] \\ &= \tbinom{n+r}{m} \left[ (m+1) \frac{n+r-m}{m+1} - r + m \right] \\ &= \tbinom{n+r}{m}n. \end{align*}\] This completes the proof. ◻

We also use the generalized hockey-stick identity.

Lemma 8 (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 completes the proof. ◻

The centered version is as follows.

Lemma 9 (Centered hockey-stick identity). Let \(n\) be a positive integer, and let \(t\), \(k\), and \(r\) be arbitrary integers. \[\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. Substituting \(a=1 -t + \tfrac{k}{2} +r\) and \(b=n-t+ \tfrac{k}{2} +r\) into Lemma [lem:generalized-hockey-stick-identity] gives \[\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. ◻

The following formula gives the multifold sum of zeroth powers.

Lemma 10 (Multifold sums of zero powers). Let \(r\) and \(n\) be nonnegative integers. \[\begin{align*} \Sigma^{r}\,{n}^{0} = \binom{r+n-1}{r}. \end{align*}\]

Proof.

  1. When \(r=0\), Definition [def:multifold-sums-of-powers-recurrence] gives \(\Sigma^{0}\,{n}^{0} = 1\).

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

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

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

  5. For general \(r\), the hockey-stick identity gives \(\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}\).

This completes the proof. ◻

Throughout, we use the following convention.

Convention 11. For all \(x\), \[\begin{align*} x^0 = 1. \end{align*}\]

Donald Knuth discusses the convention \(x^0=1\) for all \(x\), including zero, in Concrete Mathematics, as described in (Graham et al. 1994, 162) and in his notes in (Knuth 1992).

Introduction

In this manuscript, we derive formulas for sums of powers by combining the central Newton interpolation formula for powers in Lemma [lem:central-newtons-formula-for-powers] with the hockey-stick identity in Lemma [lem:centered-hockey-stick-identity]. We showcase the algorithm for finding closed forms for sums of powers of integers, as proposed in (Kolosov 2026a, Alg. (11.2)). More precisely, the main idea is to identify the binomial basis in variants of Newton’s formula associated with different 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*}\] Each variant of Newton’s formula above has a corresponding 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 bases allow us to combine Newton’s formula with a hockey-stick identity to obtain closed forms for sums of powers. Thus, we focus on closed forms for sums of powers using the central Newton formula and the hockey-stick identity in Lemma [lem:centered-hockey-stick-identity].

Main Results

We begin with Lemma [lem:central-newtons-formula-for-powers], which gives Newton’s interpolation formula for powers. Applying Lemma [lem:central-factorials-binomial-form] to this formula, for non-negative integers \(n\) and \(m\) and an arbitrary integer \(t\), gives \[\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*}\] Notice that the factor \(n\binom{n-t+\frac{k}{2}-1}{k-1}\) prevents us from direct use of hockey-stick identity [lem:generalized-hockey-stick-identity]. The binomial decomposition in Lemma [lem:binomial-decomposition] handles this factor. Substituting \(r=-t+\frac{k}{2}-1\) and \(m=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*}\] For clarity, applying Lemma [lem:binomial-decomposition] directly gives \[\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*}\] Combining the terms involving \(t\binom{n-t+\frac{k}{2}-1}{k-1}\) and simplifying the factors of \(k\) gives \[\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 absorb the term \(t^m\) into the sum to obtain \[\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*}\] We now 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 remove the fractional coefficient. Set \(a=n-t+\frac{k}{2}-1\). \[\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*}\] The upper indices of the binomial coefficients may be fractional, because \(\binom{n}{k}\) is a polynomial in \(n\). The identity involving the unsigned Stirling numbers of the first kind \(\genfrac{[}{]}{0pt}{}{n}{k}\) makes this explicit: \[\begin{align*} \binom{n}{k} = \sum_{j=0}^{k} \frac{(-1)^{k-j}}{k!} \genfrac{[}{]}{0pt}{}{k}{j} n^j. \end{align*}\] The following example illustrates the identity.

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

We can now apply the centered hockey-stick identity in Lemma [lem:centered-hockey-stick-identity] to obtain a closed formula for sums of powers: \[\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*}\] Applying Lemma [lem:centered-hockey-stick-identity] gives \[\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*}\] We obtain the following closed formula for ordinary sums of powers.

Proposition 13 (Ordinary sums of powers). Let \(n\) and \(m\) be nonnegative integers, and let \(t\) be an arbitrary integer. \[\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*}\]

The following example illustrates the formula.

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, setting \(r=0\) and \(r=1\) in Lemma [lem:centered-hockey-stick-identity] gives \[\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*}\] We can now state the formula for double sums of powers.

Proposition 15 (Double sums of powers). Let \(n\) and \(m\) be nonnegative integers, and let \(t\) be an arbitrary integer. \[\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*}\]

The following example illustrates the double-sum formula.

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

The general case is as follows.

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

Lemma [lem:multifold-sum-of-zero-powers] gives the following formula in binomial form.

Proposition 18 (Multifold Binomial sums of powers). Let \(r\), \(n\), and \(m\) be nonnegative integers, and let \(t\) be an arbitrary integer. \[\begin{align*} \Sigma^{r+1}\,{n}^{m} &= \frac{1}{2} \sum_{k=0}^{m} \Bigg[ \binom{n-t+\frac{k}{2}+r}{k+r+1} + \binom{n-t+\frac{k}{2}+r+1}{k+r+1} \\ &- \sum_{s=0}^{r} \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-1}{r-s} \Bigg] \delta^{k} t^{m}. \end{align*}\]

We have therefore derived closed formulas for multifold sums of powers. The case of forward finite differences \(\Delta\) and Newton’s formula is given in (Kolosov 2025); it follows the algorithm proposed in (Kolosov 2026a, Alg. (11.2)). The case of multifold formulas using backward differences \(\nabla\) and Newton’s formula is given in (Kolosov 2026b).

Remark on Knuth’s Formula

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

Proposition 19 (Knuth’s odd powers sum). Let \(n\) be a nonnegative integer, and let \(m\) be a positive integer. \[\begin{align*} \Sigma^{1}\,{n}^{2m-1} = \sum_{k=1}^{m} (2k-1)! \binom{n+k}{2k} T(2m,2k), \end{align*}\] where \(T(2m,2k)\) are central factorial numbers of the second kind.

The sequences A008957, A036969, and A269945 list central factorial numbers of the second kind \(T(n,k)\) in the OEIS, as described in (Sloane et al. 2003). Table 1 lists initial values of \(T(2n,2k)\).

Central factorial numbers of the second kind \(T(2n,2k)\).
\(n/k\) 0 1 2 3 4 5 6 7
0 1
1 0 1
2 0 1 1
3 0 1 5 1
4 0 1 21 14 1
5 0 1 85 147 30 1
6 0 1 341 1408 627 55 1
7 0 1 1365 13013 11440 2002 91 1

It is interesting to notice that Proposition [prop:knuth-odd-powers-sum] directly follows from Central Newton’s Formula in Lemma [lem:central-newtons-formula-for-powers], evaluated at zero. For \(m\geq 1\), the formula gives \[\begin{align*} n^{2m} = \sum_{k=1}^{2m} \frac{n^{[k]}}{k!} \cdot \delta^{k} 0^{2m}. \end{align*}\] The term for \(k=0\) vanishes because \(\delta^{0} 0^{2m} = 0\) when \(m\geq1\). For positive integers \(m\) and \(k\), the central difference \(\delta^k 0^m\) is nonzero exactly when \(k\leq m\) and \(m\) and \(k\) have the same parity: \[\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*}\] In particular, the difference vanishes when \(m\) and \(k\) have opposite parity. This parity property applies to powers evaluated at zero; for example, \(\delta^{3}1^{4}=24\neq0\). Since \(2m\) is even, the differences \(\delta^{k}0^{2m}\) vanish for odd \(k\), so we may omit those terms: \[\begin{align*} n^{2m} = \sum_{k=1}^{m} \frac{n^{[2k]}}{(2k)!} \cdot \delta^{2k} 0^{2m}. \end{align*}\] By the definition of the central factorial numbers of the second kind, we obtain \[\begin{align*} n^{2m} = \sum_{k=1}^{m} n^{[2k]} T(2m,2k). \end{align*}\] Therefore, \[\begin{align*} n^{2m} = \sum_{k=1}^{m} (2k)! \frac{n^{[2k]}}{(2k)!} T(2m,2k). \end{align*}\] Applying Lemma [lem:central-factorials-binomial-form] to simplify \(\frac{n^{[2k]}}{(2k)!}\) gives \[\begin{align*} n^{2m} = \sum_{k=1}^{m} (2k)! \frac{n}{2k} \binom{n+k-1}{2k-1} T(2m,2k). \end{align*}\] Consequently, \[\begin{align*} n^{2m} = \sum_{k=1}^{m} (2k-1)! n \binom{n+k-1}{2k-1} T(2m,2k). \end{align*}\] Factoring out \(n\) gives \[\begin{align*} n^{2m-1} &= \sum_{k=1}^{m} (2k-1)! \binom{n+k-1}{2k-1} T(2m,2k). \end{align*}\] Applying the hockey-stick identity \(\sum_{k=0}^{n} \binom{k}{j} = \binom{n+1}{j+1}\) gives \[\begin{align*} \Sigma^{1}\,{n}^{2m-1} = \sum_{k=1}^{m} (2k-1)! \binom{n+k}{2k} T(2m,2k). \end{align*}\] This formula agrees with Proposition [prop:knuth-odd-powers-sum]. Repeated application of the hockey-stick identity \(\sum_{k=0}^{n} \binom{k}{j} = \binom{n+1}{j+1}\) generalizes the formula to multifold sums.

Proposition 20 (Knuth’s odd powers sum multifold). Let \(r\) and \(n\) be nonnegative integers, and let \(m\) be a positive integer. \[\begin{align*} \Sigma^{r+1}\,{n}^{2m-1} = \sum_{k=1}^{m} (2k-1)! \binom{n+k+r}{2k+r} T(2m,2k), \end{align*}\] where \(T(2m,2k)\) are central factorial numbers of the second kind.

The following example illustrates Proposition [prop:knuth-odd-powers-sum].

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

The following example illustrates Proposition [prop:knuth-odd-powers-sum-multifold].

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 in Proposition [prop:knuth-odd-powers-sum-multifold] form the sequence A303675 in the OEIS, as listed in (Sloane et al. 2003). Proposition [prop:knuth-odd-powers-sum-multifold] also motivates the following identity. Combining Newton’s formula in Lemma [lem:central-newtons-formula-for-powers] with Lemma [lem:central-factorials-binomial-form] gives \[\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*}\] Factoring out \(n\) gives \[\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*}\] Shifting the exponent gives \[\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*}\] Re-indexing the sum gives \[\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}\] Setting \(r=0\) and \(t=\frac{1}{2}\) in Lemma [lem:centered-hockey-stick-identity] gives the following proposition.

Proposition 23 (Ordinary sums of powers at zero). Let \(n\) and \(m\) be nonnegative integers. \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{k=0}^{m} \left[ \binom{n+\frac{k}{2}+\frac{1}{2}}{k+1} - \binom{\frac{k}{2}+\frac{1}{2}}{k+1}\right] \frac{\delta^{k+1} 0^{m+1}}{k+1}. \end{align*}\]

The formula can also be written 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*}\] Setting \(r=1\) and \(t=\frac{1}{2}\) in Lemma [lem:centered-hockey-stick-identity] gives a formula for double sums of powers.

Proposition 24 (Double sums of powers at zero). Let \(n\) and \(m\) be nonnegative integers. \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{k=0}^{m} \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] \frac{\delta^{k+1} 0^{m+1}}{k+1}. \end{align*}\]

The general formula is as follows.

Theorem 25 (Multifold sums of powers at zero). Let \(r\), \(n\), and \(m\) be nonnegative integers. \[\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]. ◻

Combining Lemma [lem:multifold-sum-of-zero-powers] with Theorem [thm:multifold-sums-of-powers-at-zero] gives the following binomial form.

Proposition 26 (Multifold sums of powers at zero binomial form). Let \(r\), \(n\), and \(m\) be nonnegative integers. \[\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]. ◻

This formula can also 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*}\] The results above follow from evaluating the central Newton formula at zero. Table 2 lists initial values of \(T(n,k)\).

Central factorial numbers of the second kind \(T(n,k)\). See also the sequences A395862, and A370703 in the OEIS (Sloane et al. 2003).
\(n/k\) 0 1 2 3 4 5 6 7 8
0 1
1 0 1
2 0 0 1
3 0 \(\tfrac{1}{4}\) 0 1
4 0 0 1 0 1
5 0 \(\tfrac{1}{16}\) 0 \(\tfrac{5}{2}\) 0 1
6 0 0 1 0 5 0 1
7 0 \(\tfrac{1}{64}\) 0 \(\tfrac{91}{16}\) 0 \(\tfrac{35}{4}\) 0 1
8 0 0 1 0 21 0 14 0 1

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 provide Wolfram Mathematica programs for the efficient verification of the derived identities.

Mathematica Programs

The Mathematica programs in the project repository validate the results listed below.

Mathematica Program Result Validated
ValidateOrdinarySumsOfPowers.txt Proposition [prop:ordinary-sums-of-powers]
ValidateDoubleSumsOfPowers.txt Proposition [prop:double-sums-of-powers]
ValidateMultifoldSumsOfPowers.txt Theorem [thm:multifold-sums-of-powers]
ValidateMultifoldBinomialSumsOfPowers.txt Proposition [prop:multifold-binomial-sums-of-powers]
ValidateOrdinarySumsOfPowersAtZero.txt Proposition [prop:ordinary-sums-of-powers-at-zero]
ValidateDoubleSumsOfPowersAtZero.txt Proposition [prop:double-sums-of-powers-at-zero]
ValidateMultifoldSumsOfPowersAtZero.txt Theorem [thm:multifold-sums-of-powers-at-zero]
ValidateMultifoldSumsOfPowersAtZeroBinomialForm.txt Proposition [prop:multifold-sums-of-powers-at-zero-binomial-form]

Metadata

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., Donald E. Knuth, and Oren Patashnik. 1994. Concrete Mathematics: A Foundation for Computer Science. 2nd ed. Addison-Wesley. https://archive.org/details/concrete-mathematics.
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. Wiley, New York. https://www.amazon.com/-/de/Combinatorial-Identities-Probability-Mathematical-Statistics/dp/0471722758.
Sloane, N. J. A. et al. 2003. The on-Line Encyclopedia of Integer Sequences. OEIS. 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. https://www.jstor.org/stable/41137516.
Steffensen, Johan Frederik. 1927. Interpolation. Williams & Wilkins. https://www.amazon.com/-/de/Interpolation-Second-Dover-Books-Mathematics-ebook/dp/B00GHQVON8.