Newton's interpolation formula and sums of powers

NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS PETRO KOLOSOV 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. Contents 1. Introduction and main results 1 2. Backward difference form 9 3. Future research 9 4. Proof of Segmented hockey stick identity 11 5. Conclusions 12 6. Acknowledgements 12 References 12 7. Mathematica programs 13 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 and Eulerian numbers. Date: December 24, 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, Central factorial numbers, Stirling numbers, Eulerian numbers, Worpitzky identity, OEIS. 1 NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 2 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) 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 an arbitrary integer t nm= m X k=0 n−t k∆ktm Thus, for an 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  NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 3 Therefore, Proposition 1.4 (Ordinary sums of powers via Newton’s series).For non-negative integers n, m and an 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 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 implies that finite differences can be expressed in terms of generalized Stirling numbers of the second kind, that is ∆jtm=j!m jt. NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 4 By considering the special cases of the proposition (1.4) for t= 4, we observe rather unexpected formulas for sums of powers, namely Σ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 apply the summation operator over the 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 an 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). □ NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 5 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 Proposition 1.6 (Triple sums of powers via Newton’s series).For non-negative integers n, m and an 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. □ NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 6 For example, given t= 4, the triple sums of powers are Σ3n0= 1 n−1 3+3 1Σ2n0−3 2Σ1n0+3 3Σ0n0 Σ3n1= 4 n−1 3+3 1Σ2n0−3 2Σ1n0+3 3Σ0n0 + 1 n−1 4−4 2Σ2n0+4 3Σ1n0−4 4Σ0n0 Σ3n2= 16 n−1 3+3 1Σ2n0−3 2Σ1n0+3 3Σ0n0 + 9 n−1 4−4 2Σ2n0+4 3Σ1n0−4 4Σ0n0 + 2 n−1 5+5 3Σ2n0−5 4Σ1n0+5 5Σ0n0 Continuing similarly, we are able to derive the formula for multifold sums of powers, which is Theorem 1.7 (Multifold sums of powers via Newton’s series).For non-negative integers r, n, m and an 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 applications of the segmented hockey stick identity (1.3). □ In its explicit form Example 1.8 (Explicit expansion of the s–sum in the r-fold case).For non-negative integers r, n, m and an arbitrary integer t, the r-fold sum Σrnmcan be written as Σrnm= m X j=0 ∆jtmh(−1)jj+t−1 j+ 1 Σr−1n0+ (−1)j+1j+t−1 j+ 2 Σr−2n0 + (−1)j+2j+t−1 j+ 3 Σr−3n0+· · · + (−1)j+r−1j+t−1 j+rΣ0n0 +n−t+r j+ri NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 7 We may observe that Proposition 1.9 (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) Proposition 1.10 (Multifold sums of powers binomial form).For non-negative integers r, n, m and an 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.11 (Multifold sums of powers binomial form reindexed).For non-negative integers r, n, m and an 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 differences of powers are closely related to Stirling numbers of the second kind Lemma 1.12 (Finite differences via Stirling numbers).For non-negative integers j, m and an arbitrary integer t ∆jtm= m X k=0 t k m j+k(j+k)! Which implies variations of the formulas for sums of powers Proposition 1.13 (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.12). □ NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 8 In general, Proposition 1.14 (Multifold sums of powers via Stirling numbers).For non-negative integers r, n, m and an arbitrary integer t Σrnm= m X j=0 m X k=0 " r X s=1 (−1)j+s−1j+t−1 j+sΣr−sn0!+n−t+r j+r#t k m j+k(j+k)! Proof. By multifold sums of powers via Newton’s series (1.7) and finite difference via Stirling numbers of the second kind (1.12). □ The proposition above can be presented in a pure binomial form as well, by means of the identity (1.9): Σrn0=r+n−1 r. In addition, we are able to express multifold sums of powers via Eulerian numbers, by expressing the forward finite difference via the Worpitzky identity [7] Lemma 1.15 (Worpitzky identity).For non-negative integers t, m tm= m X k=0 m kt+k m where n kare Eulerian numbers. Thus, Lemma 1.16 (Finite difference via Eulerian numbers).For non-negative integers j, m and an arbitrary integer t ∆jtm= m X k=0 m kt+k m−j Therefore, Proposition 1.17 (Multifold sums of powers via Eulerian numbers).For non-negative integers r, n, m and an arbitrary integer t Σrnm= m X j=0 m X k=0 " r X s=1 (−1)j+s−1j+t−1 j+sΣr−sn0!+n−t+r j+r#m kt+k m−j Proof. By multifold sums of powers via Newton’s series (1.7) and finite difference via Eulerian numbers of the second kind (1.16). □ NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 9 2. Backward difference form The formula for multifold sums of powers via Newton’s series (1.7) can be altered to be in terms of backward differences easily, because ∇j(t+ 1)m= ∆jtm Thus, Proposition 2.1 (Multifold sums of powers via backward difference).For non-negative integers r, n, m and an arbitrary integer t Σrnm= m X j=0 ∇j(t+ 1)m" r X s=1 (−1)j+s−1j+t−1 j+sΣr−sn0!+n−t+r j+r# Proof. By multifold sums of powers via Newton’s series (1.7) and the identity ∇j(t+ 1)m= ∆jtm.□ 3. Future research In this manuscript we focus on the idea to combine the Newton’s interpolation formula and the hockey-stick family identities 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 becomes to utilize an interpolation formula for power nmin terms of an 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, or central differences. For instance, 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 Devaluated at some point kand the hockey-stick family identity over the binomial coefficients n k Σ1nm=X k D(nm, k)X j≤nf(j) k