Iterative Procedure for Hypersums of Powers of Integers

José Luis Cereceda Distrito Telefónica, Edificio Este 1 28050 Madrid Spain

                    jl.cereceda@movistar.es

Abstract Relying on a recurrence relation for the hypersums of powers of integers put forward recently, we develop an iterative procedure which allows us to express a hypersum of arbitrary order in terms of ordinary (zeroth order) power sums. Then, we derive the coefficients of the hypersum polynomial as a function of the Bernoulli numbers and the Stirling numbers of the first kind.

1 Introduction

For every integer m, m ≥ 1, the hypersums of powers of integers are defined recursively as follows: P_{k}^{(m)}(n) = ∑_{j=1}^{n} P_{k}^{(m−1)}(j), where P_{k}^{(0)}(n) is the sum of the first n positive integers each raised to the integer power k ≥ 0, P_{k}^{(0)}(n) = 1^{k} + 2^{k} + ⋯ + n^{k} [1, 2]. The latter is given by a polynomial in n of degree k + 1 with zero constant term. Hence, inductively P_{k}^{(m)}(n) is given by a polynomial in n of degree k + m + 1 with zero constant term:

P_{k}^{(m)}(n) = ∑_{r=1}^{k+m+1} c_{k,m}^{r}n^{r}.  (1)

An explicit formula for the coefficients c_{k,m}^{r} involving the Stirling numbers of the first and second kinds has been given by the author [3]. In this paper (Section 2), by an iterative procedure, we obtain a new representation of the m-th order hypersum P_{k}^{(m)}(n) in terms of ordinary (zeroth order) power sums. Specifically, we will show that P_{k}^{(m)}(n) can be expressed as a linear combination of P_{k}^{(0)}(n), P_{k+1}^{(0)}(n), …, P_{k+m}^{(0)}(n), as follows:

P_{k}^{(m)}(n) = ∑_{i=0}^{m} \frac{(−1)^{i}q_{m,i}(n)}{m!}P_{k+i}^{(0)}(n),  (2)

where q_{m,i}(n) is a polynomial in n of degree m − i. (Note that formula (2) holds for m = 0 if we set q_{0,0}(n) = 1.) In Section 3, we determine the explicit form of the coefficients of q_{m,i}(n). Then, using (2), we obtain the coefficients c_{k,m}^{r} in terms of the Bernoulli numbers B_{k} and the (unsigned) Stirling numbers of the first kind \left[{n \atop k}\right] (see \underline{A008275} in [4]). In particular, we proved that

c_{k,m}^{1} = \frac{1}{m!} ∑_{i=0}^{m}(−1)^{i} [\begin{matrix}m + 1 \\ i + 1 \end{matrix}] B_{k+i},  (3)

in accordance with the result obtained by Inaba [2, Proposition 1]. (Please note that, throughout this paper, we use the convention that B_{1} = \frac{1}{2}.)

For later reference, we recall that the recurrence relation defining the numbers \left[{n \atop k}\right] is given by [5, p. 214]:

[\begin{matrix}m + 1 \\ i + 1 \end{matrix}] = m [\begin{matrix}m \\ i + 1 \end{matrix}] + [\begin{matrix}m \\ i \end{matrix}] ,  (4)

with \left[{0 \atop 0}\right] = 1, and \left[{n \atop 0}\right] = \left[{0 \atop n}\right] = 0 for n ≥ 1.

Formula (2) is noteworthy since it neatly shows how the hypersum P_{k}^{(m)}(n) is constructed out of the building blocks P_{k+i}^{(0)}(n), i = 0, 1, …, m. Moreover, we point out that the polynomials q_{m,i}(n) are interesting in their own right. Indeed, for fixed m, the coefficients corresponding to the set of polynomials {q_{m,i}(n)}_{i=0}^{m} may be arranged in a Pascal-like triangular array with a specific rule of formation.

2 Iterative procedure for the hypersum

The basic tool we use to obtain P_{k}^{(m)}(n) in terms of ordinary power sums is the following recurrence relation, a proof of which has been given by the author [3, Theorem 8]:

Theorem 1. The hypersums P_{k}^{(j)}(n), P_{k}^{(j−1)}(n), and P_{k+1}^{(j−1)}(n) satisfy the recurrence relation

P_{k}^{(j)}(n) = \frac{n + j}{j} P_{k}^{(j−1)}(n) − \frac{1}{j}P_{k+1}^{(j−1)}(n), k ≥ 0, j ≥ 1.  (5)

To obtain P_{k}^{(m)}(n), we repeatedly apply the recurrence (5) to successive values of j = 1, 2, …, up to j = m. Proceeding in this way, it is easy to see that, for example,

P_{k}^{(3)}(n) = \frac{1}{6}(n + 1)(n + 2)(n + 3)P_{k}^{(0)}(n)

− \frac{1}{6}[(n + 1)(n + 2) + (n + 1)(n + 3) + (n + 2)(n + 3)]P_{k+1}^{(0)}(n)

+ \frac{1}{6}[(n + 1) + (n + 2) + (n + 3)]P_{k+2}^{(0)}(n) − \frac{1}{6}P_{k+3}^{(0)}(n),

which is of the form (2) with q_{3,0}(n) = (n + 1)(n + 2)(n + 3), q_{3,1}(n) = (n + 1)(n + 2) + (n + 1)(n + 3) + (n + 2)(n + 3), q_{3,2}(n) = (n + 1) + (n + 2) + (n + 3), and q_{3,3}(n) = 1.

From this procedure, the general form of the polynomial q_{m,i}(n) is argued to be

q_{m,i}(n) = ∑_{1≤s_{1}<s_{2}<···<s_{m−i}≤m} ∏_{t=1}^{m−i}(n + s_{t}), i = 0, 1, …, m,  (6)

where s_{t}, t = 1, 2, …, m − i, is an integer. Note the special cases q_{m,m−1}(n) = ∑_{i=1}^{m}(n + i) and q_{m,0}(n) = ∏_{i=1}^{m}(n + i). Furthermore,

q_{m,i}(0) = ∑_{1≤s_{1}<s_{2}<···<s_{m−i}≤m} ∏_{t=1}^{m−i} s_{t} = σ_{m−i}(1, 2, …, m),  (7)

where σ_{m−i}(1, 2, …, m) is the (m − i)-th elementary symmetric polynomial evaluated on the first m integers {1, 2, …, m} [6, Chapter 6].

Lemma 2. For m ≥ 1, the polynomials q_{m,i}(n) satisfy the recurrence relation

(n + m)q_{m−1,i}(n) = q_{m,i}(n) − q_{m−1,i−1}(n), i = 0, 1, …, m − 1,  (8)

where it is understood that q_{m−1,i−1}(n) = 0 for i = 0.

Proof. Relation (8) follows directly from the definition of q_{m,i}(n). Hence, from (6), we obtain

(n + m)q_{m−1,i}(n) = ∑_{1≤s_{1}<···<s_{m−i−1}≤m−1} ∏_{t=1}^{m−i−1}(n + s_{t})(n + m).  (9)

On the other hand, we have

q_{m−1,i−1}(n) = ∑_{1≤s_{1}<···<s_{m−i}≤m−1} ∏_{t=1}^{m−i}(n + s_{t}).  (10)

Clearly, the sum of the right-hand side of (9) and (10) is identical to (6).

Now we show by induction on m that P_{k}^{(m)}(n) have the form (2) with q_{m,i}(n) given by (6). This statement is readily verified for the base cases m = 0, 1, 2, and 3. Assuming the inductive hypothesis holds for P_{k}^{(m−1)}(n) (with m ≥ 1), Equation (5) yields

P_{k}^{(m)}(n) = \frac{1}{m!} [(n + m) ∑_{i=0}^{m−1}(−1)^{i}q_{m−1,i}(n)P_{k+i}^{(0)}(n) − ∑_{i=0}^{m−1}(−1)^{i}q_{m−1,i}(n)P_{k+i+1}^{(0)}(n)] .

Using (8), it follows that

P_{k}^{(m)}(n) = \frac{1}{m!} [∑_{i=0}^{m−1}(−1)^{i}q_{m,i}(n)P_{k+i}^{(0)}(n)

− ∑_{i=1}^{m−1}(−1)^{i}q_{m−1,i−1}(n)P_{k+i}^{(0)}(n) + ∑_{i=1}^{m}(−1)^{i}q_{m−1,i−1}(n)P_{k+i}^{(0)}(n)]

= \frac{1}{m!} [∑_{i=0}^{m−1}(−1)^{i}q_{m,i}(n)P_{k+i}^{(0)}(n) + (−1)^{m}q_{m−1,m−1}(n)P_{k+m}^{(0)}(n)]

= \frac{1}{m!} ∑_{i=0}^{m}(−1)^{i}q_{m,i}(n)P_{k+i}^{(0)}(n),

where we used that q_{m−1,m−1}(n) = q_{m,m}(n) = 1 to justify the last equation. This completes the inductive step and the proof of the above statement. We formally state this result in the following theorem.

Theorem 3. The hypersum P_{k}^{(m)}(n) admits a representation of the form (2) with q_{m,i}(n) given by (6).

3 The coefficients of the hypersum polynomial

In this section, we provide an explicit expression for the coefficients c_{k,m}^{r} in terms of the Bernoulli numbers and the Stirling numbers of the first kind. To this end, we first put q_{m,i}(n) in polynomial form as q_{m,i}(n) = ∑_{s=0}^{m−i} q_{m,i}^{s}n^{s}. On the other hand, according to the well-known Bernoulli formula, P_{k+i}^{(0)}(n) can be written as [7, Equation 9]

P_{k+i}^{(0)}(n) = \frac{1}{k + i + 1} ∑_{t=1}^{k+i+1} \binom{k + i + 1}{t}B_{k+i+1−t}n^{t}.

(Remember that we are taking B_{1} = \frac{1}{2} in the above formula.) Then, substituting the aforementioned expressions for q_{m,i}(n) and P_{k+i}^{(0)}(n) into (2) and comparing the resulting polynomial with (1), gives

c_{k,m}^{r} = \frac{1}{m!} ∑_{i=0}^{m}(−1)^{i}Q_{k,m,i}^{r}, r = 1, 2, …, k + m + 1,  (11)

where

Q_{k,m,i}^{r} = \frac{1}{k + i + 1} ∑_{h=0}^{r−1} q_{m,i}^{h}\binom{k + i + 1}{r − h}B_{k+i+h+1−r}.  (12)

In particular, from (11) and (12), we quickly obtain

c_{k,m}^{1} = \frac{1}{m!} ∑_{i=0}^{m}(−1)^{i}q_{m,i}^{0}B_{k+i}, k, m ≥ 0.  (13)

Now let us address the question of the nature of the coefficients q_{m,i}^{s}, s = 0, 1, …, m − i, of q_{m,i}(n). Let us first look at the constant term q_{m,i}^{0}. This is the value of q_{m,i}(n) at n = 0. Hence, from (7), we have q_{m,i}^{0} = σ_{m−i}(1, 2, …, m). On the other hand, the Stirling numbers of the first kind \left[{n \atop k}\right] enumerate all the permutations of size n with k cycles. It turns out that σ_{k}(1, 2, …, n) = \left[{n+1 \atop n+1−k}\right] [5, pp. 213–214], and then

σ_{m−i}(1, 2, …, m) = [\begin{matrix}m + 1 \\ i + 1 \end{matrix}] .  (14)

Thus, we have q_{m,i}^{0} = \left[{m+1 \atop i+1}\right]. Putting this in (13), we obtain formula (3).

In order to systematically derive the coefficients q_{m,i}^{s}, it is useful to note that

∏_{t=1}^{m−i}(n + s_{t}) = ∑_{s=0}^{m−i} σ_{m−i−s}(s_{1}, s_{2}, …, s_{m−i})n^{s},

where σ_{m−i−s}(s_{1}, s_{2}, …, s_{m−i}) is the (m − i − s)-th elementary symmetric polynomial on the variables s_{1}, s_{2}, …, s_{m−i}. Substituting this expression into (6), we deduce that

q_{m,i}^{s} = ∑_{1≤s_{1}<s_{2}<···<s_{m−i}≤m} σ_{m−i−s}(s_{1}, s_{2}, …, s_{m−i}).  (15)

Clearly, the right-hand side of (15) is a symmetric function on {s_{1}, s_{2}, …, s_{m−i}}. This function is a sum of products of m − i − s distinct integers chosen from {1, 2, …, m}, with a total of \binom{m}{i} times \binom{m−i}{s} terms. On the other hand, the elementary symmetric polynomial σ_{m−i−s}(1, 2, …, m) is a sum of \binom{m}{i+s} terms, each of which is a product of m − i − s distinct integers chosen from \{1, 2, …, m\}. Therefore, since \binom{m}{i}\binom{m−i}{s} = \binom{i+s}{s}\binom{m}{i+s}, we conclude that the right-hand side of (15) is necessarily \binom{i+s}{s} times σ_{m−i−s}(1, 2, …, m). Hence, using (14), we find that

q_{m,i}^{s} = \binom{i + s}{s} [\begin{matrix}m + 1 \\ i + s + 1 \end{matrix}] , s = 0, 1, …, m − i.  (16)

Note, in particular, that q_{m,i}^{m−i} = \binom{m}{i}. From (16), we also deduce the symmetry property q_{m,i}^{s} = q_{m,s}^{i}. As a concrete example, Table 1 displays the coefficients of the polynomials q_{8,i}(n), i = 0, 1, …, 8, where we use [n^{s}] to denote the coefficient of n^{s}. Note that the

[n^{0}]  [n^{1}]  [n^{2}]  [n^{3}] [n^{4}] [n^{5}] [n^{6}] [n^{7}] [n^{8}]
q_{8,8}(n)  1  –  –  –  –  –  –  –  –
q_{8,7}(n) 36  8  –  –  –  –  –  –  –
q_{8,6}(n) 546  252  28  –  –  –  –  –  –
q_{8,5}(n) 4536 3276  756  56  –  –  –  –  –
q_{8,4}(n) 22449 22680 8190 1260 70  –  –  –  –
q_{8,3}(n) 67284 89796 45360 10920 1260 56  –  –  –
q_{8,2}(n) 118124 201852 134694 45360 8190 756 28 –  –
q_{8,1}(n) 109584 236248 201852 89796 22680 3276 252 8  –
q_{8,0}(n) 40320 109584 118124 67284 22449 4536 546 36 1

Table 1: The coefficients of the polynomials q_{8,i}(n), i = 0, 1, …, 8.

symmetry property implies that the table of coefficients is symmetric about a 45^{∘} diagonal. For example, we have q_{8,2}^{4} = q_{8,4}^{2} = 8190.

Finally, combining the Equations (11), (12), and (16), we obtain

c_{k,m}^{r} = \frac{1}{m!} ∑_{i=0}^{m} \frac{(−1)^{i}}{k + i + 1} ∑_{h=0}^{r−1} \binom{i + h}{h}\binom{k + i + 1}{r − h}[\begin{matrix}m + 1 \\ i + h + 1 \end{matrix}] B_{k+i+h+1−r},

which constitutes the generalization of Inaba’s formula (3) to arbitrary r = 1, 2, …, k+m+1, with k, m ≥ 0, and B_{1} = \frac{1}{2}.

On the other hand, from (8), we immediately derive the following recurrence relation for the coefficients q_{m,i}^{s}:

q_{m,i}^{s} = mq_{m−1,i}^{s} + q_{m−1,i−1}^{s} + q_{m−1,i}^{s−1}.  (17)

For s = 0, relation (17) becomes q_{m,i}^{0} = mq_{m−1,i}^{0}+q_{m−1,i−1}^{0}. Therefore, comparing this relation with (4) and noting that q_{0,0}^{0} = 1 = \left[{1 \atop 1}\right], we retrieve the result q_{m,i}^{0} = \left[{m+1 \atop i+1}\right]. For s = 1 we have q_{m,i}^{1} = mq_{m−1,i}^{1} + q_{m−1,i−1}^{1} + q_{m−1,i}^{0}, which is satisfied when we set q_{m,i}^{1} = (i + 1)q_{m,i+1}^{0} = (i + 1)\left[{m+1 \atop i+2}\right]. In general, the solution of the recurrence (17) is given by

q_{m,i}^{s} = \frac{1}{s}(i + 1)q_{m,i+1}^{s−1}

= \frac{1}{s} \frac{1}{s − 1}(i + 1)(i + 2)q_{m,i+2}^{s−2}

⋮

= \frac{1}{s!}(i + 1)(i + 2) ⋯ (i + s)q_{m,i+s}^{0},

so that q_{m,i}^{s} = \binom{i+s}{s}q_{m,i+s}^{0} = \binom{i+s}{s}\left[{m+1 \atop i+s+1}\right], in accordance with (16).

Thus, Table 1 is generated by the rule q_{m,i}^{s} = \frac{1}{s}(i + 1)q_{m,i+1}^{s−1}, s ≥ 1, which enables one to determine the element q_{m,i}^{s} in row m − i and column s from the preceding element q_{m,i+1}^{s−1} in row m − i − 1 and column s − 1, the elements of the starting 0-th column being given by q_{m,i}^{0} = \left[{m+1 \atop i+1}\right].

We conclude with three brief remarks.

Remark 4. For k = 0 the hypersum P_{k}^{(m)}(n) is equal to P_{0}^{(m)}(n) = \binom{n+m}{m+1}. Then, letting

k = 0 in (2), we will have ∑_{i=0}^{m} \frac{(−1)^{i}q_{m,i}(n)}{m!}P_{i}^{(0)}(n) = \binom{n+m}{m+1}. Solving for P_{m}^{(0)}(n), we get

(−1)^{m}P_{m}^{(0)}(n) = m!\binom{n + m}{m + 1} + ∑_{i=0}^{m−1}(−1)^{i+1}q_{m,i}(n)P_{i}^{(0)}(n), m ≥ 1,

which allows us to compute recursively P_{m}^{(0)}(n) from the power sums P_{0}^{(0)}(n), P_{1}^{(0)}(n), …, P_{m−1}^{(0)}(n), and the polynomials q_{m,i}(n), i = 0, 1, …, m − 1.

Remark 5. The leading coefficient of the hypersum polynomial (1) has been given by the author [3]: c_{k,m}^{k+m+1} = \frac{k!}{(k+m+1)!}. On the other hand, the leading coefficients of q_{m,i}(n) and

P_{k+i}^{(0)}(n) are given by q_{m,i}^{m−i} = \binom{m}{i} and c_{k+i,0}^{k+i+1} = \frac{1}{k+i+1}, respectively. Therefore, equating the terms of maximum degree on the two sides of (2) yields the combinatorial identity

∑_{i=0}^{m} \frac{(−1)^{i}}{k + i + 1}\binom{m}{i} = \frac{k! m!}{(k + m + 1)!}, k, m ≥ 0.

Remark 6. From formula (3), we deduce an identity relating the harmonic number H_{m} = 1 + \frac{1}{2} + ⋯ + \frac{1}{m} to the Bernoulli numbers and the Stirling numbers of the first kind. Indeed, from c_{0,m}^{1} = 1/(m + 1) [2, 3], recalling that \left[{m+1 \atop 2}\right] = m!H_{m}, and from (3) we obtain

H_{m} = \frac{2m}{m + 1} + \frac{2}{m!} ∑_{j=1}^{⌊m/2⌋} [\begin{matrix}m + 1 \\ 2j + 1 \end{matrix}] B_{2j}.

4 Acknowledgement

The author would like to thank an anonymous referee for giving an extensive list of comments and suggestions that led to an improvement of an earlier version of this paper.

References

[1] D. E. Knuth, Johann Faulhaber and sums of powers, Math. Comp. 61 (1993), 277–294.

[2] Y. Inaba, Hyper-sums of powers of integers and the Akiyama-Tanigawa matrix, J. Integer Sequences 8 (2005), Article 05.2.7.

[3] J. L. Cereceda, Generalized Akiyama-Tanigawa algorithm for hypersums of powers of integers, J. Integer Sequences 16 (2013), Article 13.3.2.

[4] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Published electronically

   at http://oeis.org.

[5] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, D. Reidel Publishing Company, 1974.

[6] W. Fulton, Young Tableaux: With Applications to Representation Theory and Geometry, Cambridge University Press, 1997.

[7] T. M. Apostol, Bernoulli’s power-sum formulas revisited, Math. Gaz. 90 (2006), 276–279.

2010 Mathematics Subject Classification: Primary 11B57; Secondary 11C08, 11Y55. Keywords: hypersum polynomial, iterative procedure, elementary symmetric polynomial, Bernoulli number, Stirling number of the first kind.

(Concerned with sequence \underline{A008275}.)

Received October 14 2013; revised versions received January 19 2014; March 17 2014. Published in Journal of Integer Sequences, March 23 2014.

Return to Journal of Integer Sequences home page.