Newton’s interpolation formula and sums of powers

Petro Kolosov

2026-01-24

Abstract

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 and Eulerian numbers.

1

Introduction and main results

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 manuscript, we use Newton’s interpolation formula in forward 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 backward and central differences can be found in (Kolosov 2026, 2025b), respectively. Allow us to start from the definition of multifold sums of powers. We utilize the recurrence proposed by Donald Knuth in his article Johann Faulhaber and sums of powers, see (Knuth, Donald E. 1993).

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

Throughout the paper, we utilize Newton’s interpolation formula (Newton, Isaac and Chittenden, N.W. 1850, Lemma V.) as stated below.

Proposition 2 (Newton’s interpolation formula). 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_{j=0}^{\infty} \binom{x-a}{j} \Delta^{j} f(a), \end{align*}\] where the \(k\)th forward finite difference of \(f\) evaluated at \(a\) is defined by \[\begin{align*} \Delta^{k} f(a) = \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} f(a+j). \end{align*}\]

Therefore, by setting \(f(n)=n^m\) yields

Proposition 3 (Newton’s formula for powers). Let \(n,m\ge 0\) be integers, and let \(t\) be an arbitrary integer. Then, \[\begin{align*} n^m = \sum_{k=0}^{m} \binom{n-t}{k} \Delta^{k} t^m. \end{align*}\]

We can see that Proposition [prop:newtons-interpolation-formula-for-powers] is indeed true, because, \[\begin{align*} n^3 &= 0 \tbinom{n-0}{0} + 1 \tbinom{n-0}{1} + 6 \tbinom{n-0}{2} + 6 \tbinom{n-0}{3}, \\ n^3 &= 1 \tbinom{n-1}{0} + 7 \tbinom{n-1}{1} + 12 \tbinom{n-1}{2} + 6 \tbinom{n-1}{3}, \\ n^3 &= 8 \tbinom{n-2}{0} + 19 \tbinom{n-2}{1} + 18 \tbinom{n-2}{2} + 6 \tbinom{n-2}{3}, \\ n^3 &= 27 \tbinom{n-3}{0} + 37 \tbinom{n-3}{1} + 24 \tbinom{n-3}{2} + 6 \tbinom{n-3}{3}. \end{align*}\]

Lemma 4 (Generalized hockey stick identity). For integers \(a \leq 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, \[\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. ◻

Therefore, shifted version of Lemma [prop:generalized-hockey-stick-identity] follows.

Lemma 5 (Shifted hockey stick identity). For integers \(n,t,j,r\), \[\begin{align*} \sum_{k=1}^{n} \binom{k-t+r}{j+r} = \sum_{k=1-t+r}^{n-t+r} \binom{k}{j+r} = \binom{n-t+r+1}{j+r+1} - \binom{1-t+r}{j+r+1}. \end{align*}\]

Recall the upper negation property of binomial coefficients.

Lemma 6 (Upper negation). For integers \(r,k\), \[\begin{align*} \binom{r}{k} = (-1)^{k} \binom{k-r-1}{k}. \end{align*}\]

Thus, \[\begin{align*} \binom{1-t+r}{j+r+1} &= (-1)^{j+r+1} \binom{(j+r+1)-(1-t+r)-1}{j+r+1} \\ &= (-1)^{j+r+1} \binom{j+t-1}{j+r+1}. \end{align*}\] Formula above implies negated version of shifted hockey-stick identity [lem:shifted-generalized-hockey-stick-identity].

Lemma 7 (Negated hockey stick identity). For integers \(n,t,j,r\), \[\begin{align*} \sum_{k=1}^{n} \binom{k-t+r}{j+r} = \binom{n-t+r+1}{j+r+1} + (-1)^{j+r} \binom{j+t-1}{j+r+1}. \end{align*}\]

Hence, by Newton’s formula for powers [prop:newtons-interpolation-formula-for-powers], we get formula for ordinary sums of powers. \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{k=1}^{n} \sum_{j=0}^{m} \binom{k-t}{j} \Delta^{j} t^m = \sum_{j=0}^{m} \Delta^{j} t^m \sum_{k=1}^{n} \binom{k-t}{j}, \end{align*}\] where \(t\) is an arbitrary integer. By shifted hockey stick identity [lem:shifted-generalized-hockey-stick-identity], the closed form of ordinary sums of powers yields.

Proposition 8 (Ordinary power sums). For integers \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \left[ \binom{n-t+1}{j+1} - \binom{1-t}{j+1} \right]. \end{align*}\]

For example, \[\begin{align*} \Sigma^{1}\,{n}^{3} &= 0\!\left[\tbinom{n+1}{1}-\tbinom{1}{1}\right] + 1\!\left[\tbinom{n+1}{2}-\tbinom{1}{2}\right] + 6\!\left[\tbinom{n+1}{3}-\tbinom{1}{3}\right] + 6\!\left[\tbinom{n+1}{4}-\tbinom{1}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 1\!\left[\tbinom{n}{2}-\tbinom{0}{2}\right] + 7\!\left[\tbinom{n}{3}-\tbinom{0}{3}\right] + 12\!\left[\tbinom{n}{4}-\tbinom{0}{4}\right] + 6\!\left[\tbinom{n}{5}-\tbinom{0}{5}\right], \\ % \Sigma^{1}\,{n}^{3} &= 8\!\left[\tbinom{n-1}{2}-\tbinom{-1}{2}\right] + 19\!\left[\tbinom{n-1}{3}-\tbinom{-1}{3}\right] + 18\!\left[\tbinom{n-1}{4}-\tbinom{-1}{4}\right] + 6\!\left[\tbinom{n-1}{5}-\tbinom{-1}{5}\right], \\ % \Sigma^{1}\,{n}^{3} &= 27\!\left[\tbinom{n-2}{2}-\tbinom{-2}{2}\right] + 37\!\left[\tbinom{n-2}{3}-\tbinom{-2}{3}\right] + 24\!\left[\tbinom{n-2}{4}-\tbinom{-2}{4}\right] + 6\!\left[\tbinom{n-2}{5}-\tbinom{-2}{5}\right]. \end{align*}\] By Lemma [lem:negated-hockey-stick-identity], we obtain negated version of Proposition [prop:ordinary-sums-of-powers-via-newtons-formula].

Proposition 9 (Negated ordinary power sums). For integers \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \left[ \binom{n-t+1}{j+1} + (-1)^j \binom{j+t-1}{j+1} \right]. \end{align*}\]

For example, \[\begin{align*} \Sigma^{1}\,{n}^{3} &= 0\!\left[\tbinom{n+1}{1} + \tbinom{-1}{1}\right] + 1\!\left[\tbinom{n+1}{2} + \tbinom{-1}{2}\right] + 6\!\left[\tbinom{n+1}{3} - \tbinom{0}{3}\right] + 6\!\left[\tbinom{n+1}{4} + \tbinom{1}{4}\right], \\ % \Sigma^{1}\,{n}^{3} &= 1\!\left[\tbinom{n}{2} + \tbinom{0}{2}\right] + 7\!\left[\tbinom{n}{3} - \tbinom{1}{3}\right] + 12\!\left[\tbinom{n}{4} + \tbinom{2}{4}\right] + 6\!\left[\tbinom{n}{5} - \tbinom{3}{5}\right], \\ % \Sigma^{1}\,{n}^{3} &= 8\!\left[\tbinom{n-1}{2} + \tbinom{1}{2}\right] + 19\!\left[\tbinom{n-1}{3} - \tbinom{2}{3}\right] + 18\!\left[\tbinom{n-1}{4} + \tbinom{3}{4}\right] + 6\!\left[\tbinom{n-1}{5} - \tbinom{4}{5}\right], \\ % \Sigma^{1}\,{n}^{3} &= 27\!\left[\tbinom{n-2}{2} + \tbinom{2}{2}\right] + 37\!\left[\tbinom{n-2}{3} - \tbinom{3}{3}\right] + 24\!\left[\tbinom{n-2}{4} + \tbinom{4}{4}\right] + 6\!\left[\tbinom{n-2}{5} - \tbinom{5}{5}\right]. \end{align*}\] By setting \(t=0\) into Proposition [prop:ordinary-sums-of-powers-via-newtons-formula] yields another well-known identity for sums of powers, see (Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren 1994, 190) and (Pfaff 2007). That is,

Corollary 10. For integers \(n \geq 0\), and \(m \geq 0\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \binom{n+1}{j+1} \Delta^{j} 0^m. \end{align*}\]

In particular, \[\begin{align*} \Sigma^{1}\,{n}^{2} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2} + 2 \tbinom{n+1}{3}, \\ \Sigma^{1}\,{n}^{3} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2} + 6 \tbinom{n+1}{3} + 6 \tbinom{n+1}{4}, \\ \Sigma^{1}\,{n}^{4} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2} + 14 \tbinom{n+1}{3} + 36 \tbinom{n+1}{4} + 24 \tbinom{n+1}{5}, \\ \Sigma^{1}\,{n}^{5} &= 0 \tbinom{n+1}{1} + 1 \tbinom{n+1}{2} + 30 \tbinom{n+1}{3} + 150 \tbinom{n+1}{4} + 240 \tbinom{n+1}{5} + 120 \tbinom{n+1}{6}. \end{align*}\] The coefficients \(0,1,2,0, 1, 6, 6, 0, 1, 14, 36, 24, \dots\) is the sequence A131689 in the OEIS (Sloane, Neil J.A. and others 2003). By setting \(t=1\) into Proposition [prop:ordinary-sums-of-powers-via-newtons-formula], we get another well-known special case.

Corollary 11. For non-negative integers \(n,m\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \binom{n}{j+1} \Delta^{j} 1^m. \end{align*}\]

For instance, \[\begin{align*} \Sigma^{1}\,{n}^{2} &= 1 \tbinom{n}{1} + 3 \tbinom{n}{2} +2 \tbinom{n}{3}, \\ \Sigma^{1}\,{n}^{3} &= 1 \tbinom{n}{1} + 7 \tbinom{n}{2} +12 \tbinom{n}{3} + 6 \tbinom{n}{4}, \\ \Sigma^{1}\,{n}^{4} &= 1 \tbinom{n}{1} +15 \tbinom{n}{2} +50 \tbinom{n}{3} +60 \tbinom{n}{4} + 24 \tbinom{n}{5}, \\ \Sigma^{1}\,{n}^{5} &= 1 \tbinom{n}{1} +31 \tbinom{n}{2} +180 \tbinom{n}{3} +390 \tbinom{n}{4} + 360 \tbinom{n}{5} + 120 \tbinom{n}{6}. \end{align*}\] The coefficients \(1,3,2,1,7,12,6,1,15, \dots\) is the sequence A028246 in the OEIS (Sloane, Neil J.A. and others 2003). It is particularly interesting that the paper (Cereceda, José L. 2022) give formulas for sums of powers in terms of generalized Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{k}{j}_{r}\). \[\begin{align} \Sigma^{1}\,{n}^{k} &= \sum_{j=0}^{k} j! \left[ \binom{n+1-r}{j+1} + (-1)^j \binom{r+j-1}{j+1} \right] \genfrac{\{}{\}}{0pt}{}{k}{j}_{r}, \label{eq:cereceda-sums-1} \\ \Sigma^{1}\,{n}^{k} &= \sum_{j=0}^{k} j! \left[ \binom{n+1-r}{j+1} + \binom{r+1}{j+1} \right] \genfrac{\{}{\}}{0pt}{}{k}{j}_{-r}. \label{eq:cereceda-sums-2} \end{align}\] Formula [eq:cereceda-sums-1] is a special case of Proposition [prop:negation-of-ordinary-sums-of-powers-via-newtons-formula], in terms of generalized Stirling numbers \(\genfrac{\{}{\}}{0pt}{}{k}{j}_{r}\). This implies that finite differences of powers can be expressed in terms of generalized Stirling numbers of the second kind, \(\Delta^{j} t^m = j! \genfrac{\{}{\}}{0pt}{}{m}{j}_{t}\). Formula [eq:cereceda-sums-2] is a special case of Proposition [prop:ordinary-sums-of-powers-via-newtons-formula] with \(t=-r\). By setting \(t=4\) into Proposition [prop:ordinary-sums-of-powers-via-newtons-formula], we observe rather unusual formulas for sums of powers, namely, \[\begin{align*} \Sigma^{1}\,{n}^{0} &= 1 \left( \tbinom{n-3}{1} + \tbinom{3}{1} \right), \\ \Sigma^{1}\,{n}^{1} &= 4 \left( \tbinom{n-3}{1} + \tbinom{3}{1} \right) + 1 \left( \tbinom{n-3}{2} - \tbinom{4}{2} \right), \\ \Sigma^{1}\,{n}^{2} &= 16 \left( \tbinom{n-3}{1} + \tbinom{3}{1} \right) + 9 \left( \tbinom{n-3}{2} - \tbinom{4}{2} \right) + 2 \left( \tbinom{n-2}{3} + \tbinom{5}{3} \right), \\ \Sigma^{1}\,{n}^{3} &= 64 \left( \tbinom{n-3}{1} + \tbinom{3}{1} \right) + 61 \left( \tbinom{n-3}{2} - \tbinom{4}{2} \right) + 30 \left( \tbinom{n-3}{3} + \tbinom{5}{3} \right) + 6 \left( \tbinom{n-3}{4} - \tbinom{6}{4} \right). \end{align*}\] The coefficients \(1,4,1,16,9,\dots\) is the sequence A391633 in the OEIS (Sloane, Neil J.A. and others 2003). In general, \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} 4^m \left[ \binom{n-3}{j+1} + (-1)^j \binom{j+3}{j+1} \right]. \end{align*}\] To derive formula for double sum of powers, we apply summation operator over the ordinary sum of powers [prop:ordinary-sums-of-powers-via-newtons-formula] again. Thus, \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \left[ \left( \sum_{k=1}^{n} \binom{k-t+1}{j+1} \right) - \binom{1-t}{j+1} \sum_{k=1}^{n} 1 \right], \end{align*}\] which implies, \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \left[ \left( \sum_{k=1}^{n} \binom{k-t+1}{j+1} \right) - \binom{1-t}{j+1} n \right]. \end{align*}\] By applying shifted hockey stick identity [lem:shifted-generalized-hockey-stick-identity], we get formula for double sums of powers.

Proposition 12 (Double sums of powers). For integers \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \left[ \binom{n-t+2}{j+1} - \binom{1-t}{j+1} n - \binom{2-t}{j+2} \right] \end{align*}\]

By applying Lemma [lem:negated-hockey-stick-identity] on Proposition [prop:double-sums-of-powers-via-newtons-formula], we obtain negated variation of formula for sums of powers.

Proposition 13 (Negated double sums of powers). For integers \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \left[ \binom{n-t+2}{j+1} + (-1)^j \binom{j+t-1}{j+1} n + (-1)^{j+1} \binom{j+t-1}{j+2} \right]. \end{align*}\]

For example, by setting \(t=5\) into Proposition [prop:negated-double-sums-of-powers-via-newtons-formula], we get, \[\begin{align*} \Sigma^{2}\,{n}^{0} &= 1 \left( \tbinom{n-3}{2} + \tbinom{4}{1} n - \tbinom{4}{2} \right), \\ \Sigma^{2}\,{n}^{1} &= 5 \left( \tbinom{n-3}{2} + \tbinom{4}{1} n - \tbinom{4}{2} \right) + 1 \left( \tbinom{n-3}{3} - \tbinom{5}{2} n + \tbinom{5}{3} \right), \\ \Sigma^{2}\,{n}^{2} &= 25 \left( \tbinom{n-3}{2} + \tbinom{4}{1} n - \tbinom{4}{2} \right) + 11 \left( \tbinom{n-3}{3} - \tbinom{5}{2} n + \tbinom{5}{3} \right) + 2 \left( \tbinom{n-3}{4} + \tbinom{6}{3} n - \tbinom{6}{4} \right). \end{align*}\] The coefficients \(1,5,1,25,11,2,\dots\) is the sequence A391635 in the OEIS (Sloane, Neil J.A. and others 2003). In general, \[\begin{align*} \Sigma^{2}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} 5^{m} \left[ \binom{n-3}{j+2} + (-1)^{j} \binom{j+4}{j+1} n^1 + (-1)^{j+1} \binom{j+4}{j+2} n^0 \right]. \end{align*}\] By summing up double sums of powers [prop:double-sums-of-powers-via-newtons-formula], we obtain non-closed expression for triple sums of powers. \[\begin{align*} \Sigma^{3}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \sum_{k=1}^{n} \left[ \binom{k-t+2}{j+1} - \binom{1-t}{j+1} k^1 - \binom{2-t}{j+2} k^0 \right]. \end{align*}\] Note that \(\sum_{k=1}^{n} k^1 = \Sigma^{2}\,{n}^{0}\) and \(\sum_{k=1}^{n} k^0 = \Sigma^{1}\,{n}^{0}\) and \(1 = \Sigma^{0}\,{n}^{0}\). Therefore, by shifted hockey stick identity [lem:shifted-generalized-hockey-stick-identity], we get the closed form identity for triple sums of powers.

Proposition 14 (Triple sums of powers). For integers \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{3}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \left[ \binom{n-t+2}{j+1} - \binom{1-t}{j+1} \Sigma^{2}\,{n}^{0} - \binom{2-t}{j+2} \Sigma^{1}\,{n}^{0} - \binom{3-t}{j+3} \Sigma^{0}\,{n}^{0} \right]. \end{align*}\]

By utilizing Lemma [lem:negated-hockey-stick-identity] on Proposition [prop:triple-sums-of-powers-via-newtons-formula] yields its negated variation.

Proposition 15 (Negated triple sums of powers). For integers \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{3}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^m \Bigg[ \binom{n-t+3}{j+3} &+ (-1)^{j} \binom{j+t-1}{j+1} \Sigma^{2}\,{n}^{0} + (-1)^{j+1} \binom{j+t-1}{j+2} \Sigma^{1}\,{n}^{0} \\ &+ (-1)^{j+2} \binom{j+t-1}{j+3} \Sigma^{0}\,{n}^{0} \Bigg]. \end{align*}\]

For instance, by setting \(t=4\) into Proposition [prop:triple-sums-of-powers-via-newtons-formula], for \(m=1\) we have, \[\begin{align*} \Sigma^{3}\,{n}^{1} &= 4 \left( \tbinom{n-1}{3} + \tbinom{3}{1} \Sigma^{2}\,{n}^{0} - \tbinom{3}{2} \Sigma^{1}\,{n}^{0} + \tbinom{3}{3} \Sigma^{0}\,{n}^{0} \right), \\ &+ 1 \left( \tbinom{n-1}{4} - \tbinom{4}{2} \Sigma^{2}\,{n}^{0} + \tbinom{4}{3} \Sigma^{1}\,{n}^{0} - \tbinom{4}{4} \Sigma^{0}\,{n}^{0} \right). \end{align*}\] For \(m=2\) we have, \[\begin{align*} \Sigma^{3}\,{n}^{2} &= 16 \left( \tbinom{n-1}{3} + \tbinom{3}{1} \Sigma^{2}\,{n}^{0} - \tbinom{3}{2} \Sigma^{1}\,{n}^{0} + \tbinom{3}{3} \Sigma^{0}\,{n}^{0} \right), \\ &+ 9 \left( \tbinom{n-1}{4} - \tbinom{4}{2} \Sigma^{2}\,{n}^{0} + \tbinom{4}{3} \Sigma^{1}\,{n}^{0} - \tbinom{4}{4} \Sigma^{0}\,{n}^{0} \right), \\ &+ 2 \left( \tbinom{n-1}{5} + \tbinom{5}{3} \Sigma^{2}\,{n}^{0} - \tbinom{5}{4} \Sigma^{1}\,{n}^{0} + \tbinom{5}{5} \Sigma^{0}\,{n}^{0} \right). \end{align*}\] The coefficients \(1,4,1,16,9,\dots\) is the sequence A391633 in the OEIS (Sloane, Neil J.A. and others 2003). In general, \[\begin{align*} \Sigma^{3}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} 4^m \Bigg[ \binom{n-1}{j+3} &+ (-1)^{j} \binom{j+3}{j+1} \Sigma^{2}\,{n}^{0} + (-1)^{j+1} \binom{j+3}{j+2} \Sigma^{1}\,{n}^{0} \\ &+ (-1)^{j+2} \binom{j+3}{j+3} \Sigma^{0}\,{n}^{0} \Bigg]. \end{align*}\] By repeated application of shifted hockey stick identity [lem:shifted-generalized-hockey-stick-identity], and Newton’s formula for powers [prop:newtons-interpolation-formula-for-powers], we derive the closed formula for multifold sums of powers.

Theorem 16 (Multifold sums of powers). For integers \(r\geq 0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^{m} \left[ \binom{n-t+r}{j+r} - \sum_{s=1}^{r} \binom{s-t}{j+s} \Sigma^{r-s}\,{n}^{0} \right]. \end{align*}\]

By negated hockey stick identity [lem:negated-hockey-stick-identity], another variation of multifold sums of powers follows.

Theorem 17 (Negated multifold sums of powers). For integers \(r\geq 0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^{m} \left[ \binom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \binom{j+t-1}{j+s} \Sigma^{r-s}\,{n}^{0} \right]. \end{align*}\]

In its explicit form, \[\begin{align*} \Sigma^{r}\,{n}^{m} = \mathop{\textstyle\sum}_{j=0}^{m} \Delta^{j} t^{m} \Big[ \tbinom{n-t+r}{j+r} &+ (-1)^{j} \tbinom{j+t-1}{j+1} \Sigma^{r-1}\,{n}^{0} + (-1)^{j+1} \tbinom{j+t-1}{j+2} \Sigma^{r-2}\,{n}^{0} + \cdots \\ &+ (-1)^{j+r-1} \tbinom{j+t-1}{j+r} \Sigma^{0}\,{n}^{0} \Big]. \end{align*}\] We may notice the identity for closed-form of \(\Sigma^{r-1}\,{n}^{0}\).

Proposition 18 (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.

  1. Let \(r=0\), then \(\Sigma^{0}\,{n}^{0}=n^0=\binom{n-1}{0} = 1\), by definition.

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

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

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

  5. 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, \[\begin{align*} \Sigma^{r-s}\,{n}^{0} = \binom{r-s+n-1}{r-s}. \end{align*}\]

Therefore, we obtain a pure binomial form of Theorem [theorem:multifold-sums-of-powers-via-newtons-formula].

Proposition 19 (Multifold Binomial sums of powers). For integers \(r\geq 0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^{m} \left[ \binom{n-t+r}{j+r} - \sum_{s=1}^{r} \binom{s-t}{j+s} \binom{r-s+n-1}{r-s} \right]. \end{align*}\]

By Lemma [lem:negated-hockey-stick-identity] on Proposition [prop:multifold-sums-of-powers-binomial-form], we obtain its negated version.

Proposition 20 (Negated multifold Binomial sums of powers). For integers \(r\geq 0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} &= \sum_{j=0}^{m} \Delta^{j} t^{m} \left[ \binom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \binom{j+t-1}{j+s} \binom{r-s+n-1}{r-s} \right]. \end{align*}\]

By re-indexing the sum in \(s\) in Proposition [prop:negated-multifold-sums-of-powers-binomial-form], we get its shifted form.

Proposition 21 (Shifted multifold Binomial sum of powers). For integers \(r\geq 0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \Delta^{j} t^{m} \left[ \binom{n-t+r}{j+r} + \sum_{s=0}^{r-1} (-1)^{j+s} \binom{j+t-1}{j+s+1} \binom{r-s+n-2}{r-s-1} \right]. \end{align*}\]

Sums of powers in Stirling numbers

Forward finite differences of powers are closely related to Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\), as the following well-known lemma shows.

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

This lemma implies variations for ordinary sums of powers. By utilizing Proposition [prop:ordinary-sums-of-powers-via-newtons-formula], and Lemma [lem:finite-differences-via-stirling-numbers], we obtain formula for sums of powers in terms of Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\).

Proposition 23 (Stirling sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n-t+1}{j+1} - \binom{1-t}{j+1} \right] \genfrac{\{}{\}}{0pt}{}{m}{j+k} \binom{t}{k} (j+k)! \end{align*}\]

In addition, by using negated formula for sums of powers in Proposition [prop:negation-of-ordinary-sums-of-powers-via-newtons-formula], with Lemma [lem:finite-differences-via-stirling-numbers] for finite differences in Stirling numbers \(\genfrac{\{}{\}}{0pt}{}{n}{k}\), we obtain new result.

Proposition 24 (Negated Stirling sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n-t+1}{j+1} + (-1)^j \binom{j+t-1}{j+1} \right] \genfrac{\{}{\}}{0pt}{}{m}{j+k} \binom{t}{k} (j+k)! \end{align*}\]

By setting \(t=0\) into Proposition [prop:negated-ordinary-sums-of-powers-via-stirling-numbers] yields well-known identity for sums of powers in terms of Stirling numbers. That is,

Corollary 25. For non-negative integers \(n,m\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \binom{n+1}{j+1} \genfrac{\{}{\}}{0pt}{}{m}{j} j! \end{align*}\]

Similarly, formula for multifold sums of powers in terms of Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\) follows.

Proposition 26 (Multifold Stirling sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n-t+r}{j+r} - \sum_{s=1}^{r} \binom{s-t}{j+s} \Sigma^{r-s}\,{n}^{0} \right] \genfrac{\{}{\}}{0pt}{}{m}{j+k} \binom{t}{k} (j+k)! \end{align*}\]

By utilizing Lemma [lem:negated-hockey-stick-identity] for negated hockey stick identity, we obtain negated version formula for multifold sums of powers in terms of Stirling numbers of the second kind \(\genfrac{\{}{\}}{0pt}{}{n}{k}\).

Proposition 27 (Negated multifold Stirling sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \tbinom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \tbinom{j+t-1}{j+s} \Sigma^{r-s}\,{n}^{0} \right] % {\textstyle\genfrac\{\}{0pt}{}{m}{j+k}}% \tbinom{t}{k} (j+k)! \end{align*}\]

Propositions [prop:multifold-stirling-sums-of-powers], and [prop:multifold-sums-of-powers-via-stirling-numbers] can be expressed in a pure binomial form, by means of identity [prop:multifold-sum-of-zero-powers], which implies that \(\Sigma^{r-s}\,{n}^{0} = \binom{r-s+n-1}{r-s}\). Therefore, we get multifold Stirling-Binomial formula for sums of powers.

Proposition 28 (Multifold Stirling-Binomial sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n-t+r}{j+r} - \sum_{s=1}^{r} \binom{s-t}{j+s} \binom{r-s+n-1}{r-s} \right] \genfrac{\{}{\}}{0pt}{}{m}{j+k} \binom{t}{k} (j+k)! \end{align*}\]

Lemma [lem:negated-hockey-stick-identity] yields its negated version.

Proposition 29 (Negated Stirling-Binomial sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \tbinom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \tbinom{j+t-1}{j+s} \tbinom{r-s+n-1}{r-s} \right] % {\textstyle\genfrac\{\}{0pt}{}{m}{j+k}}% \tbinom{t}{k} (j+k)! \end{align*}\]

Sums of powers in Eulerian numbers

Forward finite differences can be expressed in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\), by means of Worpitzky identity (Worpitzky 1883).

Lemma 30 (Worpitzky identity). For non-negative integers \(t,m\) \[\begin{align*} t^{m} = \sum_{k=0}^{m} \binom{t+k}{m} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}, \end{align*}\] where \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\) are Eulerian numbers.

Thus, we obtain formula for finite differences of powers, in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\).

Lemma 31 (Eulerian finite differences). For integers \(j,m \geq 0\) and an arbitrary integer \(t\), \[\begin{align*} \Delta^{j} t^{m} = \sum_{k=0}^{m} \binom{t+k}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}. \end{align*}\]

Hence, by multifold sums of powers [theorem:multifold-sums-of-powers-via-newtons-formula], and by Lemma [lem:finite-differences-via-eulerian-numbers], we get formula for multifold sums of powers in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\).

Proposition 32 (Multifold Eulerian sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n-t+r}{j+r} - \sum_{s=1}^{r} \binom{s-t}{j+s} \Sigma^{r-s}\,{n}^{0} \right] \binom{t+k}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}. \end{align*}\]

In addition, by negated multifold sums of powers [theorem:negated-multifold-sums-of-powers-via-newtons-formula], and by Lemma [lem:finite-differences-via-eulerian-numbers], yields negated version of Proposition [prop:multifold-eulerian-sums-of-powers].

Proposition 33 (Negated multifold Eulerian sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} =\sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \binom{j+t-1}{j+s} \Sigma^{r-s}\,{n}^{0} \right] \binom{t+k}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}. \end{align*}\]

In particular,

Proposition 34 (Negated Eulerian sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n-t+1}{j+1} + (-1)^j \binom{j+t-1}{j+1} \right] \binom{t+k}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}. \end{align*}\]

By setting \(t=0\) into Proposition [prop:sums-of-powers-via-eulerian-numbers] yields a well-known identity for sums of powers in terms of Eulerian numbers \(\genfrac{\langle}{\rangle}{0pt}{}{n}{k}\).

Corollary 35 (Eulerian sums of powers in zero). For integers \(n\geq 0\), and \(m\geq 0\), \[\begin{align*} \Sigma^{1}\,{n}^{m}= \sum_{j=0}^{m} \sum_{k=0}^{m} \binom{n+1}{j+1} \binom{k}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}. \end{align*}\]

By Propositions [prop:multifold-sums-of-powers-binomial-form], and [prop:negated-multifold-sums-of-powers-binomial-form], we obtain a formula for multifold sums of powers in Eulerian-Binomial form. That is,

Proposition 36 (Multifold Eulerian-Binomial sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \binom{n-t+r}{j+r} - \sum_{s=1}^{r} \binom{s-t}{j+s} \binom{r-s+n-1}{r-s} \right] \binom{t+k}{m-j} \genfrac{\langle}{\rangle}{0pt}{}{m}{k}. \end{align*}\]

While its negated form is,

Proposition 37 (Negated multifold Eulerian-Binomial sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \sum_{k=0}^{m} \left[ \tbinom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \tbinom{j+t-1}{j+s} \tbinom{r-s+n-1}{r-s} \right] \tbinom{t+k}{m-j} % {\textstyle\genfrac\langle\rangle{0pt}{}{m}{k}}% . \end{align*}\]

Backward difference form

Formula for multifold sums of powers [theorem:multifold-sums-of-powers-via-newtons-formula] can be expressed in terms of backward differences easily, because,

Proposition 38. For integers \(j,m,t\), \[\begin{align*} \Delta^{j} t^{m} = \nabla^{j} (t+j)^{m}. \end{align*}\]

Therefore, by Proposition [prop:forward-via-backward-differences], we get formula for sums of powers in terms of backward differences.

Proposition 39 (Multifold backward sums of powers). For integers \(r,n,m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \left[ \binom{n-t+r}{j+r} - \sum_{s=1}^{r} \binom{s-t}{j+s} \Sigma^{r-s}\,{n}^{0} \right] \nabla^{j} (t+j)^{m}. \end{align*}\]

By Theorem [theorem:negated-multifold-sums-of-powers-via-newtons-formula] and by Proposition [prop:forward-via-backward-differences] yields negated formula for sums of powers.

Proposition 40 (Negated backward sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\) \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \left[ \binom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \binom{j+t-1}{j+s} \Sigma^{r-s}\,{n}^{0} \right] \nabla^{j} (t+j)^{m}. \end{align*}\]

By Proposition [prop:multifold-sums-of-powers-binomial-form] and by negated Binomial sums of powers [prop:negated-multifold-sums-of-powers-binomial-form], we obtain multifold sums of powers in Binomial form.

Proposition 41 (Multifold backward binomial sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \left[ \binom{n-t+r}{j+r} - \sum_{s=1}^{r} \binom{s-t}{j+s} \binom{r-s+n-1}{r-s} \right] \nabla^{j} (t+j)^{m}. \end{align*}\]

By negated hockey-stick identity [lem:negated-hockey-stick-identity], the negated formula for sums of powers follows.

Proposition 42 (Negated backward binomial sums of powers). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} &= \sum_{j=0}^{m} \left[ \binom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \binom{j+t-1}{j+s} \binom{r-s+n-1}{r-s} \right] \nabla^{j} (t+j)^{m}. \end{align*}\]

By re-indexing the sum in \(s\) gives its shifted variation.

Proposition 43 (Shifted multifold backward Binomial sums). For integers \(r\geq0\), and \(n\geq 0\), and \(m\geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \left[ \binom{n-t+r}{j+r} + \sum_{s=0}^{r-1} (-1)^{j+s} \binom{j+t-1}{j+s+1} \binom{r-s+n-2}{r-s-1} \right] \nabla^{j} (t+j)^{m}. \end{align*}\]

Central difference form

Theorem [theorem:multifold-sums-of-powers-via-newtons-formula] can be expressed in terms of central differences easily, because,

Proposition 44. For integers \(j,m,t\), \[\begin{align*} \Delta^{j} t^{m} = \delta^{j} \left( t+ \frac{j}{2} \right)^{m}. \end{align*}\]

Thus, by negated multifold sums of powers [theorem:negated-multifold-sums-of-powers-via-newtons-formula] and by Proposition [prop:forward-via-central-differences], we obtain formula for multifold sums of powers in terms of central differences \(\delta\).

Proposition 45 (Multifold central sums of powers). For integers \(r,n,m \geq 0\), and an arbitrary integer \(t\), \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{j=0}^{m} \left[\binom{n-t+r}{j+r} + \sum_{s=1}^{r} (-1)^{j+s-1} \binom{j+t-1}{j+s} \Sigma^{r-s}\,{n}^{0} \right] \delta^{j} \left( t + \frac{j}{2} \right)^m. \end{align*}\]

Future research

In this manuscript, we focus on derivation of formulas for sums of powers, by combining Newton’s formula for powers [prop:newtons-interpolation-formula-for-powers] and hockey stick identities [prop:generalized-hockey-stick-identity], and [lem:shifted-generalized-hockey-stick-identity]. This idea, however, can be generalized even further. Hence, we are free to utilize interpolation formulas for powers in terms of generalized difference operator \(D\), and binomial coefficients \(\binom{f(n)}{k}\). We are not limited to linear difference operators \(\Delta, \nabla\) and \(\delta\). There is a complete theory on dynamic differential equations on time-scales, founded by Bohner and Peterson in (Bohner, Martin and Peterson, Allan 2001). In general, dynamic differential operators assume that the rate of function’s change \(h\) is represented by another function \(g(h)\), which is not necessary a linear one. For example, the Jackson’s derivative (Jackson, Frederick H. 1909) is as follows. \[\begin{align*} D_q(f(x)) = \frac{f(qx) - f(x)}{qx-x}. \end{align*}\] Thus, finding interpolation formula for \(f(x)=x^n\) in terms of \(D_q(f(x))\) implies new formulas for sums of powers. In general, let be an abstract interpolation formula for powers, \[\begin{align*} n^m = \sum_{k} \binom{f(n)}{k} D(n^m, k). \end{align*}\] Therefore, we obtain one of formulas for sums of powers, that involves the abstract difference operator \(D\), evaluated at the point \(k\). By hockey stick identity for binomial coefficients \(\binom{n}{k}\), we get its closed form. \[\begin{align*} \Sigma^{1}\,{n}^{m} = \sum_{k} D(n^m, k) \sum_{j \leq n} \binom{f(j)}{k}. \end{align*}\] Similarly, for multifold sums of powers, \[\begin{align*} \Sigma^{r}\,{n}^{m} = \sum_{k} D(n^m, k) \binom{f(n+r)}{k}. \end{align*}\] Many interpolation approaches involve rising factorials \(x^{\left(n\right)}\), or falling factorials \(\left(x\right)_{n}\), or regular factorials \(n!\), hence can be expressed in terms of binomial coefficients, because, \[\begin{align*} \frac{\left(x\right)_{n}}{n!} = \binom{x}{n}; \quad \frac{x^{\left(n\right)}}{n!} = \binom{x+n-1}{n}; \quad x^{[n]} = n \left(x+\frac{n}{2}-1\right)_{n-1}. \end{align*}\] In particular, Donald Knuth provides the formula for multifold sums of odd powers in (Knuth, Donald E. 1993).

Proposition 46 (Multifold sums of odd powers). For non-negative integers \(r,n,m\) \[\begin{align*} \Sigma^{r}\,{n}^{2m-1} &= \sum_{k=1}^{m} \binom{n+k-1+r}{2k-1+r} \frac{1}{2k} \delta^{2k} 0^{2m} \\ &= \sum_{k=1}^{m} \binom{n+k-1+r}{2k-1+r} (2k-1)! T(2m, 2k), \end{align*}\] where \(T(n,k)\) are the central factorial numbers of the second kind, see (Steffensen, Johan Frederik 1927, sec. 58) and (Carlitz and Riordan 1963, formula (10a)).

This formula originates from Newton’s formula in central differences, evaluated at zero, see (Kolosov 2025b). The reason is that central factorial numbers can be expressed in term of central differences of nothing. \[\begin{align*} T(n, k) = \frac{1}{k!} \delta^k 0^n = \frac{1}{k!} \sum_{j=0}^{k} (-1)^j \binom{k}{j} \left( \frac{k}{2} - j \right)^n. \end{align*}\] In general, the central factorial numbers of the second kind \(T(n,k)\) are defined by polynomial identity (Riordan 1968, ch. 6.5, formula (24)). Thus,

Lemma 47 (Riordan power identity). For integers \(n,m \geq 0\), \[\begin{align*} n^m = \sum_{k=1}^{m} T(m,k) n^{[k]}. \end{align*}\] where \(n^{[k]}\) are central factorials \(n^{[k]} = n \prod_{j=0}^{k-1} \left( n + \frac{k}{2} -j \right)\), with \(n^{[0]}=1\) for all \(n\).

The sequence A008957 in the OEIS (Sloane, Neil J.A. and others 2003) is the sequence of central factorial numbers of the second kind \(T(2n,2k)\). As future research direction, the Knuth’s formula [prop:knuth-sums-of-odd-powers] utilizes the operator of central finite differences evaluated in zero. Thus, it is worth to investigate the existence of sums of odd powers involving the central differences evaluated at an arbitrary integer point \(t\), similar to Theorems [theorem:multifold-sums-of-powers-via-newtons-formula], and [theorem:negated-multifold-sums-of-powers-via-newtons-formula].

Conclusions

In this manuscript we have derived 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, and Eulerian numbers. In addition, in [sec:future-research] we discuss the future research directions that may lead to a complete framework for sums of powers, by means of combining interpolation approaches, binomial coefficients and variations of hockey stick identity for binomial coefficients. The most important results of this manuscript are validated using Mathematica programs; see Section [sec:mathematica-programs].

Acknowledgements

I am grateful to Markus Scheuer for his valuable contribution of the list of references (Markus Scheuer 2020) about the fact that central factorial numbers of the second kind arise from central differences of nothing.

Mathematica programs

Use the Mathematica package (Kolosov 2025a) to validate the results

Mathematica Function Validates / Prints
MultifoldSumOfPowersRecurrence[r, n, m] Computes \(\Sigma^{r}\,{n}^{m}\)
ValidateOrdinarySumsOfPowersViaNewtonsSeries[5] Validates Prop. [prop:negation-of-ordinary-sums-of-powers-via-newtons-formula]
ValidateDoubleSumsOfPowersViaNewtonsSeries[5] Validates Prop. [prop:negated-double-sums-of-powers-via-newtons-formula]
ValidateMultifoldSumsOfPowersViaNewtonsSeries2[5] Validates Thm. [theorem:multifold-sums-of-powers-via-newtons-formula]
ValidateMultifoldSumsOfPowersViaNewtonsSeries[5] Validates Thm. [theorem:negated-multifold-sums-of-powers-via-newtons-formula]
ValidateFiniteDifferenceViaStirlingNumbers[10] Validates Lem. [lem:finite-differences-via-stirling-numbers]
ValidateFiniteDifferenceViaEulerianNumbers[10] Validates Lem. [lem:finite-differences-via-eulerian-numbers]
ValidateMultifoldSumsOfPowersViaCentralDifferences[5] Validates Prop. [prop:multifold-sums-of-powers-via-central-differences]
ValidateMultifoldSumsOfPowersViaBackwardDifferences[5] Validates Prop. [prop:multifold-sums-of-powers-via-backward-difference]
ValidateMultifoldSumsOfPowersViaStirlingNumbers[5] Validates Prop. [prop:multifold-sums-of-powers-via-stirling-numbers]
ValidateMultifoldSumsOfPowersViaEulerianNumbers[5] Validates Prop. [prop:multifold-sums-of-powers-via-eulerian-numbers]
ValidateMultifoldSumsOfPowersBinomialForm[5] Validates Prop. [prop:negated-multifold-sums-of-powers-binomial-form]
ValidateMultifoldSumsOfPowersBinomialFormReindexed[5] Validates Prop. [prop:negated-multifold-sums-of-powers-binomial-form-reindexed]
ValidateMultifoldSumOfZeroPowers[10] Validates Prop. [prop:multifold-sum-of-zero-powers]

Metadata

Bohner, Martin and Peterson, Allan. 2001. Dynamic equations on time scales: An introduction with applications. Https://web.mst.edu/~bohner/sample.pdf; Springer Science & Business Media.
Carlitz, L., and John Riordan. 1963. “The Divided Central Differences of Zero.” Canadian Journal of Mathematics 15: 94–100. https://doi.org/10.4153/CJM-1963-010-8.
Cereceda, José L. 2022. “Sums of powers of integers and generalized Stirling numbers of the second kind.” arXiv preprint arXiv:2211.11648. https://arxiv.org/abs/2211.11648.
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.
Jackson, Frederick H. 1909. “XI.—on q-functions and a certain difference operator.” Earth and Environmental Science Transactions of the Royal Society of Edinburgh 46 (2): 253–81.
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. 2025a. Mathematica Programs for Finite Differences, Stirling Numbers, and Sums of Powers. Https://github.com/kolosovpetro/NewtonsInterpolationFormulaAndSumsOfPowers/tree/main/mathematica.
Kolosov, Petro. 2025b. Sums of Powers via Central Finite Differences and Newton’s Formula. Https://doi.org/10.5281/zenodo.18096789; Zenodo. https://doi.org/10.5281/zenodo.18096789.
Kolosov, Petro. 2026. Sums of Powers via Backward Finite Differences and Newton’s Formula. Https://doi.org/10.5281/zenodo.18118011; Zenodo. https://doi.org/10.5281/zenodo.18118011.
Markus Scheuer. 2020. Reference request: identity in central factorial numbers. Https://math.stackexchange.com/a/3665722/463487.
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.
Pfaff, Thomas J. 2007. “Deriving a Formula for Sums of Powers of Integers.” Pi Mu Epsilon Journal 12 (7): 425–30. https://www.jstor.org/stable/24340705.
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, 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.

  1. DOI: https://doi.org/10.5281/zenodo.18040979↩︎