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. Contents 1. Introduction and main results 2 2. Backward difference form 8 3. Future research 9 4. Proof of Segmented hockey stick identity 10 5. Conclusions 11 6. Acknowledgements 12 References 12 7. Mathematica programs 13 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 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) 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 NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 3 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 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 NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 4 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 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). □ 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 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 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) 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)! NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 7 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 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.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. In addition, we are capable to express multifold sums of powers via Eulerian numbers, by expressing the forward finite difference via Worpitzky identity [7] Lemma 1.14 (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, NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 8 Lemma 1.15 (Finite difference via Eulerian numbers).For non-negative integers j, m and arbitrary integer t ∆jtm= m X k=0 m kt+k m−j Therefore, Proposition 1.16 (Multifold sums of powers via Eulerian numbers).For non-negative integers r, n, m and 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.15). □ 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 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 ∇j(t+ 1)m= ∆jtm.□ NEWTON’S INTERPOLATION FORMULA AND SUMS OF POWERS 9 3. 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 Proposition 3.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