Newton's interpolation formula and sums of powers

NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS PETRO KOLOSOV Abstract. In this manuscript we derive the formulas for multifold sums of powers by utilizing Newton’s interpolation formula. Furthermore, this manuscript provides the 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 the formulas for multifold sums of powers by utilizing Newton’s interpolation formula. Furthermore, this manuscript provides the formulas for multifold sums of powers in terms of Stirling numbers of the second kind, and Eulerian numbers. 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 [1] Σ0nm=nm Σ1nm= Σ01m+ Σ02m+· · · + Σ0nm Σr+1 nm= Σr1m+ Σr2m+· · · + Σrnm Throughout the paper, we utilize the Newton’s interpolation formula as stated below Proposition 1.1. (Newton’s series around arbitrary point [2, Lemma V].) f(x) = ∞ X j=0 x−a j∆jf(a) Date: December 23, 2025. 2010 Mathematics Subject Classification. 05A19, 05A10, 41A15, 11B83. Key words and phrases. Sums of powers, Newton’s interpolation formula, Finite differences, Binomial coefficients, Faulhaber’s formula, Bernoulli numbers, Bernoulli polynomials, Interpolation, Combinatorics, Pascal’s triangle, Central factorial numbers, OEIS. 1 NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 2 where ∆kf(x) = Pk j=0(−1)k−jk jf(x+j)is k-degree forward finite difference of f. Which indeed holds, because n3= 0n 0+ 1n 1+ 6n 2+ 6n 3 n3= 1n−1 0+ 7n−1 1+ 12n−1 2+ 6n−1 3 n3= 8n−2 0+ 19n−2 1+ 18n−2 2+ 6n−2 3 Proposition 1.2 (Newton’s series for power).For non-negative integers m, n and arbitrary integer t nm= m X k=0 n−t k∆ktm Thus, for arbitrary integer t, the ordinary sum of powers is Σ1nm= n X k=1 m X j=0 −t+k j∆jtm= m X j=0 ∆jtm n X k=1 −t+k j Proposition 1.3 (Segmented Hockey stick identity).For integers n, t and j n X k=0 −t+k j= (−1)jj+t j+ 1+n−t+ 1 j+ 1  Therefore, Proposition 1.4 (Ordinary sums of powers via Newton’s series).For non-negative integers n, m and arbitrary integer t Σ1nm= m X j=0 ∆jtm(−1)jj+t−1 j+ 1 +n−t+ 1 j+ 1  Proof. Ordinary sum of powers is given by Σ1nm=Pm j=0 ∆jtmPn k=1 −t+k j, where Pn k=1 −t+k j= (−1)jj+t−1 j+1 +n−t+1 j+1 by means of segmented hockey stick identity (1.3). □ The special cases for t= 0 and t= 1 are widely known and appear in literature quite frequently. For t= 0 and m= 3 we have the famous identity Σ1n3= 0n+ 1 1+ 1n+ 1 2+ 6n+ 1 3+ 6n+ 1 4 NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 3 which was discussed in [3, p. 190] and in [4]. The coefficients 0,1,6,6,0,1,14,36,24, . . . are given by the sequence A131689 in the OEIS [5]. The special cases for t= 1 and m= 2,3,4,5 were discussed in [6]. For instance, Σ1n3= 1n 1+ 7n 2+ 12n 3+ 6n 4 Σ1n4= 1n 1+ 15n 2+ 50n 3+ 60n 4+ 24n 5 The coefficients 1,7,12,6,1,15, . . . are given by the sequence A028246 in the OEIS [5]. Interestingly enough that the paper [6] gives the formula for sums of powers Σ1nk= k X j=0 j!n+ 1 −r j+ 1 + (−1)jr+j−1 j+ 1 k jr where k jrare generalized Stirling numbers of the second kind. The formula above is identical to the proposition (1.4), which yields that finite differences can be expressed in terms of generalized Stirling numbers of the second kind, that is ∆jtm=j!m jt. By considering the special cases of the proposition (1.4) for t= 4, we observe rather unexpected formulas for sums of powers, that are Σ1n0= 1 n−3 1+3 1 Σ1n1= 4 n−3 1+3 1+ 1 n−3 2−4 2 Σ1n2= 16 n−3 1+3 1+ 9 n−3 2−4 2+ 2 n−2 3+5 3 Σ1n3= 64 n−3 1+3 1+ 61 n−3 2−4 2+ 30 n−3 3+5 3 + 6 n−3 4−6 4 The coefficients 1,4,1,16,9, . . . are given by the sequence A391633 in the OEIS [5]. To obtain the formula for double sum of powers, we simply apply summation operator over the NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 4 ordinary sum of powers again, thus Σ2nm= m X j=0 ∆jtm"(−1)j n X k=1 j+t−1 j+ 1 + n X k=1 k−t+ 1 j+ 1 # which yields Σ2nm= m X j=0 ∆jtm"(−1)jj+t−1 j+ 1 n+ n X k=1 k−t+ 1 j+ 1 # Thus, Proposition 1.5 (Double sums of powers via Newton’s series).For non-negative integers n, m and arbitrary integer t Σ2nm= m X j=0 ∆jtm(−1)jj+t−1 j+ 1 n+ (−1)j+1j+t−1 j+ 2 n0+n−t+ 2 j+ 2  Proof. We have Σ2nm=Pm j=0 ∆jtmh(−1)jj+t−1 j+1 n+Pn k=1 k−t+1 j+1 i, where Pn k=1 k−t+1 j+1 = (−1)j+1j+t−1 j+2 n0+n−t+2 j+2 by means of segmented hockey stick identity (1.3). □ For example, given t= 5, the double sums of powers are Σ2n0= 1 n−3 2+4 1n−4 2 Σ2n1= 5 n−3 2+4 1n−4 2+ 1 n−3 3−5 2n+5 3 Σ2n2= 25 n−3 2+4 1n−4 2+ 11 n−3 3−5 2n+5 3 + 2 n−3 4+6 3n−6 4 Σ2n3= 125 n−3 2+4 1n−4 2+ 91 n−3 3−5 2n+5 3 + 36 n−3 4+6 3n−6 4+ 6 n−3 5−7 4n+7 5 The coefficients 1,5,1,25,11,2, . . . are given by the sequence A391635 in the OEIS [5]. Similarly, we obtain the formula for the triple sums of powers NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 5 Proposition 1.6 (Triple sums of powers via Newton’s series).For non-negative integers n, m and arbitrary integer t Σ3nm= m X j=0 ∆jtm"(−1)jj+t−1 j+ 1 Σ2n0+ (−1)j+1j+t−1 j+ 2 Σ1n0+ + (−1)j+2j+t−1 j+ 3 Σ0n0+n−t+ 3 j+ 3 # Proof. By summing up the double powers sums, we get Σ3nm= m X j=0 ∆jtm n X k=1 (−1)jj+t−1 j+ 1 k1+ (−1)j+1j+t−1 j+ 2 k0+k−t+ 2 j+ 2  = m X j=0 ∆jtm"(−1)jj+t−1 j+ 1 n X k=1 k1+ (−1)j+1j+t−1 j+ 2 n X k=1 k0+ n X k=1 k−t+ 2 j+ 2 # Note that Pn k=1 k1= Σ2n0and Pn k=1 k0= Σ1n0. Thus, n X k=1 k−t+ 2 j+ 2 = (−1)j+2j+t−1 j+ 3 Σ0n0+n−t+ 3 j+ 3  by segmented hockey stick identity (1.3). This completes the proof. □ Theorem 1.7 (Multifold sums of powers via Newton’s series).For non-negative integers r, n, m and arbitrary integer t Σrnm= m X j=0 ∆jtm" r X s=1 (−1)j+s−1j+t−1 j+sΣr−sn0!+n−t+r j+r# Proof. By Newton’s series for power (1.2) and repeated segmented hockey stick identity (1.3). □ We may observe that Proposition 1.8 (Multifold sum of zero powers).For integers rand n Σrn0=r+n−1 r Proof. By hockey stick identity Pt k=0 j+k j=j+t+1 j+1 .□ Which yields the following binomial variations of the Multifold sums of powers (1.7) NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 6 Proposition 1.9 (Multifold sums of powers binomial form).For non-negative integers r, n, m and arbitrary integer t Σrnm= m X j=0 ∆jtm" r X s=1 (−1)j+s−1j+t−1 j+sr−s+n−1 r−s!+n−t+r j+r# Proposition 1.10 (Multifold sums of powers binomial form reindexed).For non-negative integers r, n, m and arbitrary integer t Σrnm= m X j=0 ∆jtm" r−1 X s=0 (−1)j+sj+t−1 j+s+ 1r−s+n−2 r−s−1!+n−t+r j+r# Finite difference of power is closely related to Stirling numbers of the second kind Lemma 1.11 (Finite difference via Stirling numbers).For non-negative integers j, m and arbitrary integer t ∆jtm= m X k=0 t k m j+k(j+k)! which implies the variations of the formulas for sums of powers Proposition 1.12 (Ordinary sums of powers via Stirling numbers).For non-negative integers n, m and arbitrary integer t Σ1nm= m X j=0 m X k=0 (−1)jj+t−1 j+ 1 +n−t+ 1 j+ 1 t k m j+k(j+k)! Proof. By ordinary sums of powers via Newton’s series (1.4) and finite difference via Stirling numbers of the second kind (1.11). □ In general, Proposition 1.13 (Multifold sums of powers via Stirling numbers).For non-negative integers r, n, m and arbitrary integer t Σrnm = m X j=0 " r X s=1 (−1)j+s−1j+t−1 j+sΣr−sn0!+n−t+r j+r#m X k=0 t k m j+k(j+k)! NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 7 Proof. By multifold sums of powers via Newton’s series (1.7) and finite difference via Stirling numbers of the second kind (1.11). □ The proposition above can be presented in a pure binomial form as well, by means of the identity (1.8): Σrn0=r+n−1 r. 2. Future research In this manuscript we focus on the idea to combine the Newton’s interpolation formula and Hockey-stick identity for binomial coefficients to express the sums of powers seamlessly. This particular idea is great, however it can be generalized even further, so that the main aim is to utilize an interpolation formula for power nmin terms of abstract difference operator D(nm) and binomial coefficients f(n) ksuch that nindicates the variable of power function. The difference operator can be arbitrary, for example: forward, backward, central differences etc. For example, the abstract interpolation formula is nm=X kf(n) kD(nm, k) Thus, the formula of sums of powers involves the abstract difference operator Din some point kand hockey stick identity over the binomial coefficients n k Σ1nm=X k D(nm, k)X j≤nf(j) k Similarly, for multifold sums of powers Σrnm=X k D(nm, k)f(n+r) k Many of interpolation approaches involve rising factorials x(n), falling factorials (x)nor usual factorials n!, and thus can be expressed in terms of binomial coefficients, because (x)n n!=x n;x(n) n!=x+n−1 n In particular, Donald Knuth provides the formula multifold sums of odd powers [1] such that based on the operator of central finite differences of power evaluated in zero, that is NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 8 Proposition 2.1 (Multifold sums of odd powers). Σrn2m−1= m X k=1 (2k−1)!T(2m, 2k)n+k−1 + r 2k−1+r = m X k=1 n+k−1 + r 2k−1+r1 2kδ2k02m where T(n, k) are central factorial numbers of the second kind, see [7, section 58] and [8, formula (10a)], such that T(n, k) = 1 k!δk0n=1 k! k X j=0 (−1)jk jk 2−jn In general, the central factorial numbers of the second kind T(n, k) were defined by Riordan in his fundamental work Combinatorial identities [9, ch. 6.5, formula (24)], via polynomial identity Lemma 2.2 (Riordan power identity). nm= m X k=1 T(m, k)n[k] where n[k]are central factorials n[k]=nQk−1 j=0 n+k 2−j. The sequence A008957 in the OEIS [5] provides non-zero central factorial numbers of the second kind T(2n, 2k). The Knuth’s formula (2.1) utilizes the operator of central finite differences of power evaluated in zero, it is worth to research the existence of the sums of odd powers involving the central differences evaluated in arbitrary integer point t, similar to multifold sums of powers via Newton’s series (1.7). 3. Proof of Segmented hockey stick identity First we split the sum Pn k=0 −t+k jinto two sub-sums so that we discuss them separately n X k=0 −t+k j= t−1 X k=0 −t+k j+ n X k=t−t+k j NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 9 We assume that the two sums above run over the partition {0,1,2,· · · ,t,· · · , n}such that t < n. Considering the sum Pt−1 k=0 −t+k jwe notice that t−1 X k=0 −t+k j=−t j+−t+ 1 j+−t+ 2 j+···+ +−t+t−2 j+−t+t−1 j Thus t−1 X k=0 −t+k j= t X k=1 −k j= t−1 X k=0 −k−1 j By means of −k j= (−1)jj+k−1 j −k−1 j=−(k+ 1) j= (−1)jj+k j Thus t−1 X k=0 −t+k j= (−1)j t−1 X k=0 j+k j= (−1)jj+t j+ 1 By means of Hockey stick identity Pt k=0 j+k j=j+t+1 j+1 . Considering the sum Pn k=t−t+k jwe notice that n X k=t−t+k j= n−t X k=0 k j Thus n X k=t−t+k j= n−t X k=0 k j=n−t+ 1 j+ 1  By means of Hockey stick identity Pt k=0 j+k j=j+t+1 j+1 . Thus n X k=0 −t+k j= (−1)jj+t j+ 1+n−t+ 1 j+ 1  This completes the proof.