An Explicit Formula for Sums of Powers of Integers in Terms of Stirling Numbers

Diffalah Laissaoui Dr Yahia Farès University of Médéa

26000 Médéa Algeria

laissaoui.diffalah74@gmail.com

Mourad Rahmani Faculty of Mathematics

University of Sciences and Technology Houari Boumediene

P. O. Box 32 El Alia Bab Ezzouar 16111 Algiers Algeria

      mrahmani@usthb.dz

Abstract

In this note we present an explicit formula for the sum of powers of the first n terms of a general arithmetic sequence in terms of Stirling numbers. We then provide an algorithm for calculating the sum of consecutive powers of integers.

1 Introduction

This paper is concerned with sums of pth powers of the first n terms of a general arithmetic sequence

S_{p,(a,d)} (n) = a^{p} + (a + d)^{p} + ⋯ + (a + (n − 1) d)^{p} , n ≥ 1

where p is a nonnegative integer, and a, d are complex numbers with d ≠ 0. In particular, we have

S_{p,(1,1)} (n) = 1^{p} + 2^{p} + 3^{p} + ⋯ + n^{p},

which has been studied extensively by many authors.

The properties of S_{p,(a,d)} (n) were obtained by Howard [4] via the following generating function

B_{0} (z) := ∑_{p≥0}S_{p,(a,d)} (n) \frac{z^{p}}{p!} = ∑_{k=0}^{n−1}e^{(a+kd)z}.  (1)

For recent articles on this subject, see [1, 6, 8].

In this note we establish a generalization of the well-known formula [3, 5, 9]

S_{p,(1,1)} (n) = ∑_{k=0}^{p}k!\left\{{p \atop k}\right\}\binom{n + 1}{k + 1}, p ≥ 1.

for the sums S_{p,(a,d)} (n). Also, we provide an algorithm for calculating the sum of the pth powers of the first n terms of a general arithmetic sequence.

First we present some definitions and notations and some results that will be useful in the rest of the paper. For x ∈ ℂ, the falling factorial (x)_{n} is defined by (x)_{0} = 1, (x)_{n} = x (x − 1) ⋯ (x − n + 1) for n > 0. The generalized binomial coefficient is defined as follows:

\binom{x}{n} = \begin{cases}\frac{(x)_{n}}{n!} , & if n ≥ 0; \\ 0, & otherwise. \end{cases}

The (signed) Stirling numbers of the first kind s (n, k) are the coefficients in the expansion

(x)_{n} = ∑_{k=0}^{n}s (n, k) x^{k}

and satisfy the recurrence relation

s (n + 1, k) = s (n, k − 1) − ns (n, k) for 1 ≤ k ≤ n.  (2)

The Stirling numbers of the second kind, denoted by \left\{{n \atop k}\right\}, are the coefficients in the expansion

x^{n} = ∑_{k=0}^{n}\left\{{n \atop k}\right\} (x)_{k} .

These numbers count the number of ways to partition a set of n elements into exactly k nonempty subsets.

For any positive integer r, the r-Stirling numbers of the second kind \left\{{n \atop k}\right\}_{r} are obviously generalizations of Stirling numbers of the second kind. These numbers count the number of partitions of a set of n objects into exactly k nonempty, disjoint subsets, such that the first r elements are in distinct subsets. The exponential generating function is given by

∑_{n≥k}\left\{{n + r \atop k + r}\right\}_{r} \frac{z^{n}}{n!} = \frac{1}{k!}e^{rz} (e^{z} − 1)^{k} .

For more details about these numbers see [2, 3].

2 Main results

First, we obtain the following result via the generalized Stirling transform method.

Theorem 1. For all n ≥ 1, non-negative integer p and complex numbers a and d (d ≠ 0), we have

S_{p,(a,d)} (n) = d^{p}∑_{k=0}^{p}k!\left\{{p \atop k}\right\} (\binom{n + \frac{a}{d}}{k + 1} − \binom{\frac{a}{d}}{k + 1}) .  (3)

Proof. Since

S_{p,(a,d)} (n) = d^{p}S_{p,(\frac{a}{d} ,1)} (n) ,

we can investigate the sums S_{p,(\frac{a}{d} ,1)} (n). It follows from (1) and [7, Theorem 4] that

A_{0} (z) = ∑_{m≥0}a_{0,m} \frac{z^{m}}{m!}

= B_{0} (ln (1 + z))

= ∑_{k=0}^{n−1} (1 + z)^{\frac{a}{d} +k}

= ∑_{m≥0} \frac{z^{m}}{m!}∑_{k=0}^{n−1} (\frac{a}{d} + k)_{m} .

Since

∑_{k=0}^{n} (x + k)_{m} := \frac{(x + n + 1)_{m+1} − (x)_{m+1}}{m + 1} ,

we can easily verify that

a_{0,m} = [z^{m}] A_{0} (z)  (4)
= m! (\binom{n + \frac{a}{d}}{m + 1} − \binom{\frac{a}{d}}{m + 1})  (5)

where [z^{n}]f(z) = f_{n} denotes the operation of extracting the coefficient of z^{n} in the formal power series f(z) = ∑_{n}f_{n} \frac{z^{n}}{n!} .

Now, from [7, Corollary 1] we get

∑_{k=0}^{m} \frac{1}{d^{p+k}} s (m, k) S_{p+k,(a,d)} (n) =

∑_{k=0}^{p}\left\{{p + m \atop k + m}\right\}_{m} (m + k)! (\binom{n + \frac{a}{d}}{m + k + 1} − \binom{\frac{a}{d}}{m + k + 1}) . (6)

and the proof is completed by letting m = 0 in the above identity.

Setting p = 0 in (6), one obtains the following recursive formula for the sum of the pth powers of the first n terms of a general arithmetic sequence involving the Stirling numbers of the first kind:

Corollary 2. We have

∑_{k=0}^{m} \frac{1}{d^{k}} s (m, k) S_{k,(a,d)} (n) = m! (\binom{n + \frac{a}{d}}{m + 1} − \binom{\frac{a}{d}}{m + 1}) .

Thus, for example, when m = 0, 1, 2, 3, we obtain

S_{0,(a,d)} (n) = n,
S_{1,(a,d)} (n) = d (\binom{n + \frac{a}{d}}{2} − \binom{\frac{a}{d}}{2}) ,
−\frac{1}{d}S_{1,(a,d)} (n) + \frac{1}{d^{2}} S_{2,(a,d)} (n) = 2 (\binom{n + \frac{a}{d}}{3} − \binom{\frac{a}{d}}{3}) ,
\frac{2}{d}S_{1,(a,d)} (n) − \frac{3}{d^{2}} S_{2,(a,d)} (n) + \frac{1}{d^{3}} S_{3,(a,d)} (n) = 6 (\binom{n + \frac{a}{d}}{4} − \binom{\frac{a}{d}}{4}) .

In the next paragraph, we propose an algorithm based on a three-term recurrence relation for calculating the pth powers of the first n terms of a general arithmetic sequence S_{p,(a,d)} (n). It is convenient to introduce the following sequence A_{p,m}^{(a,d)} (n) with two indices by

A_{p,m} := A_{p,m}^{(a,d)} (n) = \frac{S_{0,(a,d)} (n)}{a_{0,m}} ∑_{k=0}^{m} \frac{1}{d^{k}} s (m, k) S_{p+k,(a,d)} (n) ,  (7)

with A_{0,m} = n and A_{p,0} = S_{p,(a,d)} (n).

Theorem 3. The sequence A_{p,m}^{(a,d)} (n) satisfies the following three-term recurrence relation

A_{p+1,m} = d\frac{a_{0,m+1}}{a_{0,m}} A_{p,m+1} + dmA_{p,m},  (8)

with the initial sequence A_{0,m} = n, and a_{0,m} is defined by (5).

Proof. From (7) and (2) , we have

A_{p,m+1} = \frac{n + 1}{a_{0,m+1}} ∑_{k=0}^{m+1} \frac{1}{d^{k}} s (m + 1, k) S_{p+k,(a,d)} (n)

= \frac{n + 1}{a_{0,m+1}} ∑_{k=1}^{m+1} \frac{1}{d^{k}} (s (m, k − 1) − ms (m, k)) S_{p+k,(a,d)} (n) .

After some rearrangement, we get

A_{p,m+1} = \frac{a_{0,m}}{da_{0,m+1}} A_{p+1,m} − \frac{a_{0,m}m}{a_{0,m+1}}A_{p,m}.

This completes the proof.

As an immediate application of (8) we have the following algorithm for evaluating Faulhaber’s formula S_{p,(1,1)} (n). Starting with the sequence R_{0,m} := n, as the first row of the matrix (R_{p,m})_{p,m≥0}, each entry is determined recursively by

R_{p+1,m} = mR_{p,m} + \frac{(m + 1) \binom{n+1}{m+2}}{\binom{n+1}{m+1} − δ_{0,m}}R_{p,m+1},

where δ_{i,j} denotes the Kronecker symbol.

Then R_{p,0} := S_{p,(1,1)} (n) is Faulhaber’s formula.

3 Acknowledgments

We thank the referee and the editor for helpful comments and suggestions.

References

[1] A. Bazsó and I. Mező, On the coefficients of power sums of arithmetic progressions. J. Number Theory 153 (2015), 117–123.

[2] A. Z. Broder, The r-Stirling numbers. Discrete Math. 49 (1984), 241–259.

[3] R. L. Graham and D. E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994.

[4] F. T. Howard, Sums of powers of integers via generating functions. Fibonacci Quart. 34 (1996), 244–256.

[5] J. Quaintance and H. W. Gould. Combinatorial Identities for Stirling Numbers: The Unpublished Notes of H. W. Gould, World Scientific Publishing, 2016.

[6] M. Merca, An alternative to Faulhaber’s formula. Amer. Math. Monthly 122 (2015), 599–601.

[7] M. Rahmani, Generalized Stirling transform. Miskolc Math. Notes 15 (2014), 677–690.

[8] R. Schumacher, An extended version of Faulhaber’s formula, J. Integer Sequences 19 (2016), Article 16.4.2.

[9] R. Wituła, K. Kaczmarek, P. Lorenc, E. Hetmaniok and M. Pleszczynski, Jordan numbers, Stirling numbers and sums of powers. Discuss. Math. Gen. Algebra Appl. 34 (2014), 155–166.

2010 Mathematics Subject Classification: Primary 11B73; Secondary 11B37. Keywords: algorithm, explicit formula, Stirling number, sums of powers of integers.

Received October 26 2016; revised version received February 24 2017. Published in Journal of Integer Sequences, February 24 2017.

Return to Journal of Integer Sequences home page.