Generalized Akiyama-Tanigawa Algorithm for Hypersums of Powers of Integers

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

                    jl.cereceda@movistar.es

Abstract In this paper we consider the hypersum polynomials, P_{k}^{(m)}(n) = ∑_{r=0}^{k+m+1} c_{k,m}^{r}n^{r}, and give an explicit formula for the coefficients c_{k,m}^{r}. We show that the c_{k,m}^{r}’s satisfy a generalized Akiyama-Tanigawa recurrence relation, thus extending some previous results due to Inaba. We also give a number of identities involving the Stirling numbers of the first and second kinds, as well as Bernoulli and harmonic numbers.

1 Introduction

Akiyama and Tanigawa, in the course of their investigation of multiple zeta values at nonpositive integers [1], found an algorithm to calculate the Bernoulli numbers in a manner similar to Pascal’s triangle for binomial coefficients. The Akiyama-Tanigawa algorithm, as reformulated by Kaneko [2] and Chen [3], is described by the sequence a_{k,m} defined recursively by

a_{k,m} = (m + 1)(a_{k−1,m} − a_{k−1,m+1}), k ≥ 1, m ≥ 0,

for a given initial sequence a_{0,m}, m = 0, 1, 2, . . .. If we start with a_{0,m} = 1/(m + 1), then it can be shown [2] that the leading element a_{k,0} is the k-th Bernoulli number B_{k} (with B_{1} = \frac{1}{2}).

Later, Inaba [4] considered hypersums of powers of integers and found that the coefficient of the first-degree term in the hypersum polynomial coincides with the element a_{k,m} of the Akiyama-Tanigawa matrix. In this paper (Section 2) we give an explicit expression for the coefficients of the hypersum polynomials in terms of the Stirling numbers of the first and second kinds. Moreover, in Section 3, we derive a recursive relationship for the hypersums. Based on this relationship, in Section 4 we show that the coefficients of the hypersum polynomials satisfy a generalized Akiyama-Tanigawa recurrence relation. Further, in Section 5, as an illustration of the general theory, we give a detailed treatment of the coefficient of the second-degree term in the hypersum polynomial, and provide the general result for the third-degree term. We conclude in Section 6 with a brief historical account of the work of Johann Faulhaber on power sums.

2 Hypersums of powers of integers

Using Inaba’s notation [4], the hypersums of powers of integers are defined recursively as

P_{k}^{(m)}(n) = ∑_{j=1}^{n} P_{k}^{(m−1)}(j), m ≥ 1,

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} + 3^{k} + ⋯ + n^{k}. There exist several formulations for P_{k}^{(0)}(n) (see, for instance, [5]). A convenient formula for our purposes is given in terms of the Stirling numbers of the second kind S(k, i) (Sloane’s \underline{A008277} [6])

P_{k}^{(0)}(n) = ∑_{i=1}^{k} i!\binom{n + 1}{i + 1}S(k, i), k ≥ 1,

with \binom{n+1}{i+1} = 0 for n < i. A detailed derivation of this formula appears, for example, in the article [7]. For hypersums of arbitrary order m this formula generalizes to [4]

P_{k}^{(m)}(n) = ∑_{i=1}^{k} i!\binom{n + m + 1}{i + m + 1}S(k, i),  k ≥ 1.  (1)

In addition, for k = 0, P_{0}^{(m)}(n) turns out to be

P_{0}^{(m)}(n) = \binom{n + m}{m + 1}.  (2)

From (1), it is readily seen that P_{k}^{(m)}(n) is a polynomial in n of degree k+m+1 with constant term zero. This follows from the fact that each \binom{n+m+1}{i+m+1} can be expanded as a polynomial in n of degree i + m + 1, and that the maximum value taken by i is k. Further, from (1) we get P_{k}^{(m)}(0) = 0 since \binom{m+1}{i+m+1} is zero for each 1 ≤ i ≤ k. Thus P_{k}^{(m)}(n) admits a polynomial representation of the form

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

with c_{k,m}^{0} = 0 for all k and m.

The following proposition gives us an explicit formula for the coefficients c_{k,m}^{r}. From now on, |s(r, t)| will denote the (unsigned) Stirling numbers of the first kind, also known as Stirling cycle numbers. (The Stirling numbers of the first kind (signed) are given by s(r, t) = (−1)^{r−t}|s(r, t)|, see \underline{A008275} in [6].)

Proposition 1. For k = 0 and 1 ≤ r ≤ m + 1, we have

c_{0,m}^{r} = \frac{1}{(m + 1)!}C(m, r),  (4)

where

C(m, r) = ∑_{t=r}^{m+1}(−1)^{m+1−t}|s(m + 1, t)|\binom{t}{r}m^{t−r}.  (5)

On the other hand, for k ≥ 1 and 1 ≤ r ≤ m + k + 1, c_{k,m}^{r} is given by

c_{k,m}^{r} = ∑_{i=max\{1,r−m−1\}}^{k} \frac{i!}{(i + m + 1)!}C(i, m, r)S(k, i),  (6)

where

C(i, m, r) = ∑_{t=r}^{i+m+1}(−1)^{i+m+1−t}|s(i + m + 1, t)|\binom{t}{r}(m + 1)^{t−r}.  (7)

Proof. Let us first prove relation (6). For that, write the hypersum P_{k}^{(m)}(n) in (1) as

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

where [n]_{k} denotes the falling factorial n(n − 1)(n − 2) ⋯ (n − k + 1). Considering n as a variable, [n+m+1]_{i+m+1} can be regarded as a polynomial in n of degree i+m+1. Therefore, to prove (6) it suffices to show that the coefficient of the r-degree term in [n + m + 1]_{i+m+1} is equal to C(i, m, r). But, by definition of the Stirling numbers of the first kind in terms of the falling factorial, [n + m + 1]_{i+m+1} can be expressed as

[n + m + 1]_{i+m+1} = ∑_{t=1}^{i+m+1}(−1)^{i+m+1−t}|s(i + m + 1, t)|(n + m + 1)^{t}.

Furthermore, by the binomial theorem we have

(n + m + 1)^{t} = ∑_{r=0}^{t} \binom{t}{r}n^{r}(m + 1)^{t−r},

and then the r-degree coefficient in (n + m + 1)^{t} is \binom{t}{r}(m + 1)^{t−r}, from which we in turn deduce that the r-degree coefficient in [n + m + 1]_{i+m+1} is just C(i, m, r). Moreover, since C(i, m, r) = 0 for i+m+1 < r, we can restrict the summation in (6) to the values i = 1, …, k if r − m ≤ 1, or else to the values i = r − m − 1, …, k if r − m ≥ 2.

Similarly, to prove (4), we first note that (2) can be written as

\binom{n + m}{m + 1} = \frac{[n + m]_{m+1}}{(m + 1)!} .

As before, [n + m]_{m+1} can be expanded as

[n + m]_{m+1} = ∑_{t=1}^{m+1}(−1)^{m+1−t}|s(m + 1, t)|(n + m)^{t}.

Since the r-degree coefficient of (n + m)^{t} is \binom{t}{r}m^{t−r} we conclude that the r-degree coefficient in [n + m]_{m+1} is equal to C(m, r), and hence the proof of (4) is done.

Next we give an alternative, closed formula for c_{0,m}^{r} that will be used later when we discuss the generalized Akiyama-Tanigawa algorithm in Section 4.

Proposition 2. For 1 ≤ r ≤ m + 1

c_{0,m}^{r} = \frac{|s(m + 1, r)|}{(m + 1)!}.  (8)

Proof. This follows immediately when we write \binom{n+m}{m+1} as

\binom{n + m}{m + 1} = \frac{[n]^{m+1}}{(m + 1)!},

where [n]^{k} denotes the rising factorial n(n+1)(n+2) ⋯ (n+k −1). To prove the proposition we have to show that |s(m + 1, r)| constitutes the r-degree term of [n]^{m+1}. But, from the algebraic definition of the (unsigned) Stirling numbers of the first kind in terms of the rising factorial, we have that

[n]^{m+1} = ∑_{r=1}^{m+1} |s(m + 1, r)|n^{r},

and thus relation (8) is proved.

A direct consequence of (8) is that, for any given r, all the coefficients c_{0,m}^{r} (m = 0, 1, 2, …) are non-negative. On the other hand, from (6) and (7) we quickly deduce the leading coefficient of P_{k}^{(m)}(n),

c_{k,m}^{k+m+1} = \frac{k!}{(k + m + 1)!},  (9)

which applies to all k ≥ 0 and m ≥ 0. Note that, as expected, for m = 0 we retrieve the well-known result c_{k,0}^{k+1} = \frac{1}{k+1}. In addition to c_{k,m}^{k+m+1}, from (6) and (7) we can also obtain closed-form expressions for the successive high-degree coefficients of P_{k}^{(m)}(n). Here we give the resultant formulas for the first five trailing coefficients next to c_{k,m}^{k+m+1}:

c_{k,m}^{k+m} = \frac{k!}{(k + m)!} \frac{m + 1}{2}, k ≥ 1, m ≥ 0,
c_{k,m}^{k+m−1} = \frac{k!}{(k + m − 1)!} \frac{(m + 1)(3m + 2)}{24}, k ≥ 2, m ≥ 0,
c_{k,m}^{k+m−2} = \frac{k!}{(k + m − 2)!} \frac{m(m + 1)^{2}}{48} , k ≥ 3, m ≥ 0,  (10)
c_{k,m}^{k+m−3} = \frac{k!}{(k + m − 3)!}(m + 1)\frac{15m^{3} + 15m^{2} − 10m − 8}{5760}, k ≥ 4, m ≥ 0,
c_{k,m}^{k+m−4} = \frac{k!}{(k + m − 4)!} \frac{m(m + 1)^{2}}{11520} (3m^{2} − m − 6), k ≥ 5, m ≥ 0.

Likewise, for m = 0, from these formulas we readily get c_{k,0}^{k} = \frac{1}{2}, c_{k,0}^{k−1} = \frac{k}{12}, c_{k,0}^{k−2} = 0, c_{k,0}^{k−3} = −\frac{k(k−1)(k−2)}{720}, and c_{k,0}^{k−4} = 0.

In the following proposition we give an alternative formula for C(i, m, r), which is most suitable for determining the low-degree coefficients of P_{k}^{(m)}(n).

Proposition 3. For 1 ≤ p ≤ m + 2 and 1 ≤ q ≤ i,

C(i, m, r) = ∑_{p+q=r+1}(−1)^{i−q}|s(m + 2, p)||s(i, q)|.  (11)

Proof. We start from the equality [n + m + 1]_{i+m+1} = \frac{1}{n}[n]^{m+2}[n]_{i}. Now, putting [n]^{m+2} = ∑_{p=1}^{m+2} |s(m + 2, p)|n^{p} and [n]_{i} = ∑_{q=1}^{i}(−1)^{i−q}|s(i, q)|n^{q}, we have

\frac{1}{n}[n]^{m+2}[n]_{i} = ∑_{p=1}^{m+2} ∑_{q=1}^{i}(−1)^{i−q}|s(m + 2, p)||s(i, q)|n^{p+q−1}.

From this expression it is clear that the r-degree coefficient in \frac{1}{n}[n]^{m+2}[n]_{i} is attained whenever p+q = r +1. Thus, recalling that C(i, m, r) denotes the coefficient of the r-degree term in [n + m + 1]_{i+m+1}, the proposition follows.

For example, for the case r = 1 we must have p = q = 1 and then

C(i, m, 1) = (−1)^{i−1}|s(m + 2, 1)||s(i, 1)| = (−1)^{i−1}(m + 1)!(i − 1)!,  (12)

where we have used the fact that |s(n, 1)| = (n − 1)!. Then, taking into account (8) and (6), we find that

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

These relations were previously derived in [4, Prop. 2]. In Section 5 we shall obtain, using relations (8), (6), and (11), the second and third-degree coefficients c_{k,m}^{2} and c_{k,m}^{3} of P_{k}^{(m)}(n).

Next we give a general expression for the leading elements c_{k,0}^{r} in terms of the Bernoulli numbers.

Proposition 4. For 1 ≤ r ≤ k + 1,

c_{k,0}^{r} = \frac{1}{k + 1}\binom{k + 1}{r}B_{k+1−r}.  (13)

with B_{1} = \frac{1}{2}.

Proof. This expression readily follows from the well-known Bernoulli formula for the ordinary power sums (see, for example, the articles [5] and [8]):

P_{k}^{(0)}(n) = \frac{1}{k + 1} ∑_{j=0}^{k} \binom{k + 1}{j}B_{j}n^{k+1−j},

where B_{1} is taken to be \frac{1}{2}. This can also be written as

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

On the other hand, recalling that c_{k,0}^{0} = 0, the polynomial (3) for m = 0 reads as

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

Thus, comparing like terms in the previous two expressions, we get (13).

From (13) we see at once that c_{k,0}^{1} = B_{k} (cf. [2]). Now Proposition 4, in conjunction with equation (6), yields the following identity.

Corollary 5. For 1 ≤ r ≤ k + 1 and k ≥ 1,

∑_{i=max\{1,r−1\}}^{k} \frac{1}{i + 1} (∑_{t=r}^{i+1}(−1)^{i+1−t}|s(i + 1, t)|\binom{t}{r})S(k, i) = \frac{1}{k + 1}\binom{k + 1}{r}B_{k+1−r}. (14)

Proof. Set m = 0 in (6) and identify the resulting expression with (13).

Putting r = 1 in (14) yields the following explicit formula for the Bernoulli numbers (with B_{1} = \frac{1}{2}):

B_{k} = ∑_{i=1}^{k} \frac{1}{i + 1} (∑_{t=1}^{i+1}(−1)^{i+1−t}|s(i + 1, t)|t)S(k, i), k ≥ 1.

Furthermore, putting m = 0 and r = 1 in (7) and equating the resulting expression to that obtained in (12) for m = 0 gives

∑_{t=1}^{i+1}(−1)^{i+1−t}|s(i + 1, t)|t = (−1)^{i−1}(i − 1)!,

and then the previous expression for B_{k} reduces to the classical identity for the Bernoulli numbers in terms of the Stirling numbers of the second kind.

Corollary 6.

B_{k} = ∑_{i=1}^{k} \frac{(−1)^{i−1}(i − 1)!}{i + 1}S(k, i), k ≥ 1.

with B_{1} = \frac{1}{2}.

3 A recursive relationship for the hypersums

In this section we derive a recursive relationship for the hypersums P_{k}^{(m)}(n) that shall constitute the core of the generalized Akiyama-Tanigawa algorithm developed in Section 4. This recurrence relation is presented in Theorem 8 below. To prove this theorem, we shall need the following preliminary result.

Lemma 7.

∑_{j=1}^{n} jP_{k}^{(m)}(j) = (n + 1)P_{k}^{(m+1)}(n) − P_{k}^{(m+2)}(n).  (15)

Proof. Set l = m + 1. Then, in view of (1), it is clear that proving (15) is tantamount to proving the combinatorial identity

∑_{j=1}^{n} j\binom{j + l}{i + l} = (n + 1)\binom{n + l + 1}{i + l + 1} − \binom{n + l + 2}{i + l + 2}.  (16)

To prove (16), we shall repeatedly use the well-known identity

∑_{j=0}^{n} \binom{j}{i} = \binom{n + 1}{i + 1},

with \binom{j}{i} = 0 for j < i. Another crucial ingredient is the absorption property

(i + 1)\binom{j + 1}{i + 1} = (j + 1)\binom{j}{i}, 0 ≤ i ≤ j,

which we rewrite in the form

j\binom{j}{i} = (i + 1)\binom{j + 1}{i + 1} − \binom{j}{i}.  (17)

With this in mind we have

∑_{j=1}^{n} j\binom{j + l}{i + l} = ∑_{j=1}^{n}(j + l)\binom{j + l}{i + l} − l ∑_{j=1}^{n} \binom{j + l}{i + l}

= ∑_{s=i+l}^{n+l} s\binom{s}{i + l} − l ∑_{s=i+l}^{n+l} \binom{s}{i + l}

= ∑_{s=i+l}^{n+l} s\binom{s}{i + l} − l\binom{n + l + 1}{i + l + 1}.

Now from relation (17) it follows that

∑_{s=i+l}^{n+l} s\binom{s}{i + l} = (i + l + 1) ∑_{s=i+l+1}^{n+l+1} \binom{s}{i + l + 1} − ∑_{s=i+l}^{n+l} \binom{s}{i + l}

= (i + l + 1)\binom{n + l + 2}{i + l + 2} − \binom{n + l + 1}{i + l + 1},

and then

∑_{j=1}^{n} j\binom{j + l}{i + l} = (i + l + 1)\binom{n + l + 2}{i + l + 2} − (l + 1)\binom{n + l + 1}{i + l + 1}.  (18)

Applying the absorption property once more, we get

(i + l + 2)\binom{n + l + 2}{i + l + 2} = (n + l + 2)\binom{n + l + 1}{i + l + 1}.

From this we obtain

(i + l + 1)\binom{n + l + 2}{i + l + 2} = (n + l + 2)\binom{n + l + 1}{i + l + 1} − \binom{n + l + 2}{i + l + 2},

and then, substituting this into (18), we retrieve the identity (16) and thus the lemma is proved.

The extended Akiyama-Tanigawa algorithm for hypersums of powers of integers is based on the following recursive relationship for the hypersums, which is stated in the next theorem.

Theorem 8. The hypersums P_{k+1}^{(m)}(n), P_{k}^{(m)}(n), and P_{k}^{(m+1)}(n) are constrained to obey the relation

P_{k+1}^{(m)}(n) = (m + 1)(P_{k}^{(m)}(n) − P_{k}^{(m+1)}(n)) + nP_{k}^{(m)}(n), k, m ≥ 0.  (19)

Proof. Assume that k and n take fixed (but otherwise arbitrary) integer values k ≥ 0 and n ≥ 1, and proceed by induction on m. First we prove the base case where m = 0. For this case we must show that

(n + 1)P_{k}^{(0)}(n) = P_{k+1}^{(0)}(n) + P_{k}^{(1)}(n).

This is most easily seen by displaying (n + 1)P_{k}^{(0)}(n) as the sum of the n + 1 rows

1^{k} + 2^{k} + 3^{k} + ⋯ + n^{k} ; 1^{k} + 2^{k} + 3^{k} + ⋯ + n^{k} ; ⋮ ; 1^{k} + 2^{k} + 3^{k} + ⋯ + n^{k} } n + 1,

and noting that this sum can be decomposed as the sum of the following two pieces

1^{k} ; 1^{k} + 2^{k} ; 1^{k} + 2^{k} + 3^{k} ; ⋮ ; 1^{k} + 2^{k} + 3^{k} + ⋯ + n^{k} } n + 1^{k} + 2^{k} + 3^{k} + ⋯ + n^{k} ; 2^{k} + 3^{k} + ⋯ + n^{k} ; 3^{k} + ⋯ + n^{k} ; ⋮ ; n^{k} } n.

Clearly, summing the rows of the piece on the left gives P_{k}^{(1)}(n). On the other hand, the entries in the i-th column of the piece on the right sum to i^{k+1}, and so the sum of all these columns amounts to P_{k+1}^{(0)}(n).

Next we take as the inductive hypothesis the assumption that, for any given m ≥ 1, it happens that

P_{k+1}^{(m−1)}(j) = m(P_{k}^{(m−1)}(j) − P_{k}^{(m)}(j)) + jP_{k}^{(m−1)}(j),  (20)

for arbitrary integers k ≥ 0 and j ≥ 1. The task is to derive (19) starting from (20). This is rather immediate once we have established Lemma 7. Indeed, recalling that, by definition,

∑_{j=1}^{n} P_{k+1}^{(m−1)}(j) = P_{k+1}^{(m)}(n), ∑_{j=1}^{n} P_{k}^{(m−1)}(j) = P_{k}^{(m)}(n), and ∑_{j=1}^{n} P_{k}^{(m)}(j) = P_{k}^{(m+1)}(n),

from (20) we obtain that

P_{k+1}^{(m)}(n) = m(P_{k}^{(m)}(n) − P_{k}^{(m+1)}(n)) + ∑_{j=1}^{n} jP_{k}^{(m−1)}(j).

From Lemma 7 we have

∑_{j=1}^{n} jP_{k}^{(m−1)}(j) = (n + 1)P_{k}^{(m)}(n) − P_{k}^{(m+1)}(n),

and then substituting this expression into the previous equation we get the recursion formula (19). Having completed the base case and the inductive case, the overall proof of Theorem 8 is done.

4 Generalized Akiyama-Tanigawa algorithm for hypersums of powers of integers

The Akiyama-Tanigawa algorithm for computing Bernoulli numbers starts with the initial row (the 0-th row) given by the sequence a_{0,m} = 1/(m + 1) (for m ≥ 0), and then generates the row k (for k ≥ 1) by the rule [2, 3, 4]

a_{k,m} = (m + 1)(a_{k−1,m} − a_{k−1,m+1}).  (21)

Then the leading element a_{k,0} of each row is seen to be the k-th Bernoulli number B_{k} with B_{1} = \frac{1}{2} [2].

As noted in the Introduction, Inaba [4] showed that the coefficient of the first-degree term in P_{k}^{(m)}(n), c_{k,m}^{1}, satisfies a recurrence relation given by (21), namely,

c_{k,m}^{1} = (m + 1)(c_{k−1,m}^{1} − c_{k−1,m+1}^{1}),  (22)

with the same initial condition c_{0,m}^{1} = 1/(m + 1), and so we have in fact that c_{k,m}^{1} = a_{k,m}. Based on Theorem 8, we are going to show that, actually, relation (22) is just a particular case of a more general relationship for the coefficients c_{k,m}^{r} of the hypersum polynomials (3). This is established in the following proposition, which constitutes one of the main results of this paper.

Proposition 9 (Generalized Akiyama-Tanigawa algorithm). For 1 ≤ r ≤ k + m + 1, k ≥ 1, and m ≥ 0, we have the recurrence relation

c_{k,m}^{r} = (m + 1)(c_{k−1,m}^{r} − c_{k−1,m+1}^{r}) + c_{k−1,m}^{r−1},  (23)

with the starting sequence given by

c_{0,m}^{r} = \frac{|s(m + 1, r)|}{(m + 1)!}.  (24)

Proof. Write the recursive relationship (19) for the hypersums as

P_{k}^{(m)}(n) = (m + 1)(P_{k−1}^{(m)}(n) − P_{k−1}^{(m+1)}(n)) + nP_{k−1}^{(m)}(n).

Replacing P_{k}^{(m)}(n) for its polynomial expression (3) (with c_{k,m}^{0} = 0) we obtain

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

or, equivalently,

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

on the understanding that c_{k−1,m}^{k+m+1} = 0. Thus, by equating like powers of n on both sides of this equation we are finally left with relation (23). On the other hand, the proof of (24) is given in Proposition 2.

Clearly, for the case r = 1 relation (23) reduces to (22), as c_{k−1,m}^{0} = 0 for all k ≥ 1 and m ≥ 0. Finally, one can check that the coefficients given in (10) in fact satisfy the recurrence (23). So, for example, for k ≥ 5 and m ≥ 0, we have that

c_{k,m}^{k+m−3} = \frac{k!}{(k + m − 3)!}(m + 1)\frac{15m^{3} + 15m^{2} − 10m − 8}{5760},
c_{k−1,m}^{k+m−3} = \frac{(k − 1)!}{(k + m − 3)!} \frac{m(m + 1)^{2}}{48} ,
c_{k−1,m+1}^{k+m−3} = \frac{(k − 1)!}{(k + m − 3)!}(m + 2)\frac{15m^{3} + 60m^{2} + 65m + 12}{5760},
c_{k−1,m}^{k+m−4} = \frac{(k − 1)!}{(k + m − 4)!}(m + 1)\frac{15m^{3} + 15m^{2} − 10m − 8}{5760},

which satisfy the relation

c_{k,m}^{k+m−3} = (m + 1)(c_{k−1,m}^{k+m−3} − c_{k−1,m+1}^{k+m−3}) + c_{k−1,m}^{k+m−4}.

5 Second-degree coefficient of the hypersum polynomial

In this section we examine explicitly the coefficient of the second-degree term in P_{k}^{(m)}(n), c_{k,m}^{2}, by means of the generalized Akiyama-Tanigawa algorithm. For r = 2, recurrence (23) becomes

c_{k,m}^{2} = (m + 1)(c_{k−1,m}^{2} − c_{k−1,m+1}^{2}) + c_{k−1,m}^{1},  (25)

with initial sequence (the row 0)

c_{0,m}^{2} = \frac{|s(m + 1, 2)|}{(m + 1)!} = \frac{H_{m}}{m + 1},  (26)

where we have used that |s(n, 2)| = (n − 1)!H_{n−1}, H_{n} denoting the harmonic number H_{n} = ∑_{i=1}^{n} 1/i, with H_{0} = 0. To obtain the sequence corresponding to row 1, c_{1,m}^{2}, we feed (26) into (25) and, recalling that c_{0,m}^{1} = 1/(m + 1), we get

c_{1,m}^{2} = \frac{H_{m+1}}{m + 2}.

Similarly, inserting this expression into (25), and noting that c_{1,m}^{1} = 1/(m + 2), we find the elements of row 2

c_{2,m}^{2} = \frac{2 + (m + 1)H_{m+1}}{(m + 2)(m + 3)} .

Likewise, proceeding this way, we obtain the sequences for rows 3 and 4 as

c_{3,m}^{2} = \frac{(m + 1)(6 + mH_{m+1})}{(m + 2)(m + 3)(m + 4)},
c_{4,m}^{2} = \frac{(m + 1)(4 + 14m + (m − 4)(m + 1)H_{m+1})}{(m + 2)(m + 3)(m + 4)(m + 5)},

\begin{matrix}k\m & 0 & 1 & 2 & 3 & 4 & 5 & ⋯ \\ 0 & 0 & 1/2 & 1/2 & 11/24 & 5/12 & 137/360 & ⋯ \\ 1 & 1/2 & 1/2 & 11/24 & 5/12 & 137/360 & 7/20 & ⋯ \\ 2 & 1/2 & 5/12 & 3/8 & 31/90 & 23/72 & 167/560 & ⋯ \\ 3 & 1/4 & 1/4 & 29/120 & 7/30 & 227/1008 & 73/336 & ⋯ \\ 4 & 0 & 1/20 & 3/40 & 113/1260 & 25/252 & 887/8400 & ⋯ \\ 5 & −1/12 & −1/12 & −11/168 & −1/21 & −23/720 & −31/1680 & ⋯ \\ 6 & 0 & −5/84 & −5/56 & −127/1260 & −13/126 & −621/6160 & ⋯ \\ 7 & 1/12 & 1/12 & 1/24 & 0 & −53/1584 & −31/528 & ⋯ \\ 8 & 0 & 7/60 & 7/40 & 361/1980 & 65/396 & 162641/1201200 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋯ \end{matrix}

Table 1: The Akiyama-Tanigawa matrix {c_{k,m}^{2}} for k = 0/8 and m = 0/5.

and so on.

In Table 1 we display the matrix for c_{k,m}^{2} that results for the first few values of k and m. From (13), it follows that the sequence corresponding to the 0-th column, c_{k,0}^{2}, k = 1, 2, 3, …, is given by c_{k,0}^{2} = \frac{1}{2}kB_{k−1}, with c_{0,0}^{2} = 0.

We can deduce a general expression for c_{k,m}^{2} by first using Proposition 3 to get C(i, m, 2), and then using (6). For r = 2 the allowed values of the ordered pair (p, q) are (1, 2) and (2, 1), and then from (11) we get

C(i, m, 2) = (−1)^{i−2}|s(m + 2, 1)||s(i, 2)| + (−1)^{i−1}|s(m + 2, 2)||s(i, 1)|.

Recalling that |s(n, 1)| = (n − 1)! and |s(n, 2)| = (n − 1)!H_{n−1}, this gives

C(i, m, 2) = (−1)^{i−2}(m + 1)!(i − 1)!H_{i−1} + (−1)^{i−1}(m + 1)!H_{m+1}(i − 1)!
= (−1)^{i−1}(m + 1)!(i − 1)!(H_{m+1} − H_{i−1}).

Provided with C(i, m, 2), we can now use (26) and (6) to obtain c_{k,m}^{2}:

Proposition 10.

c_{k,m}^{2} = \begin{cases}\frac{H_{m}}{m + 1}, & if k = 0, \\ ∑_{i=1}^{k} \frac{(−1)^{i−1}(m + 1)!(i − 1)!i!(H_{m+1} − H_{i−1})}{(i + m + 1)!}S(k, i), & if k ≥ 1. \end{cases}

The following corollary gives us an alternative explicit formula for the Bernoulli numbers in terms of the Stirling numbers of the second kind and the harmonic numbers.

Corollary 11.

B_{k} = \frac{2}{k + 1} ∑_{i=1}^{k+1} \frac{(−1)^{i−1}(i − 1)!(1 − H_{i−1})}{i + 1}S(k + 1, i), k ≥ 0.

with B_{1} = \frac{1}{2}.

Proof. We already know that c_{k,0}^{2} = \frac{1}{2}kB_{k−1} for k ≥ 1 or, equivalently, c_{k+1,0}^{2} = \frac{1}{2}(k + 1)B_{k} for k ≥ 0. Then put m = 0 in the second relation of Proposition 10 and shift k to k + 1. Equal the resulting expression to \frac{1}{2}(k + 1)B_{k}, and hence the corollary follows.

In the same way, by applying relations (8), (6), and (11), one can determine the successive low-degree coefficients c_{k,m}^{3}, c_{k,m}^{4}, . . .. In the following proposition we give the expression for c_{k,m}^{3} (note that, in this case, we have c_{0,0}^{3} = c_{0,1}^{3} = c_{1,0}^{3} = 0.)

Proposition 12.

c_{k,m}^{3} = \begin{cases}\frac{1}{2(m + 1)}((H_{m})^{2} − H_{m}^{(2)}), & if k = 0, \\ ∑_{i=1}^{k} \frac{(−1)^{i−1}(m + 1)!(i − 1)!i!}{2(i + m + 1)!}((H_{m+1} − H_{i−1})^{2} − H_{m+1}^{(2)} − H_{i−1}^{(2)})S(k, i), & if k ≥ 1, \end{cases}

where H_{m}^{(2)} = ∑_{i=1}^{m} 1/i^{2}.

6 Concluding remarks

In his 1631 Academia Algebrae, the German mathematician and engineer Johann Faulhaber (1580–1635) presented novel formulas for (in our notation) P_{k}^{(0)}(n) for values of k ranging from k = 13 up to k = 23. (He had previously published formulas for P_{k}^{(0)}(n) up to k = 12). These formulas were expressed for the first time in terms of the variable N = n(n + 1)/2. Moreover, Faulhaber also produced remarkable formulas for sums of power sums. Indeed, as Knuth explains in his comprehensive study of Faulhaber’s work on sums of powers [9], he exhibited a totally correct 17-degree polynomial in n for the hypersum P_{6}^{(10)}(n) (which in Knuth’s notation is Σ^{11}n^{6}) that, in Knuth’s words, would have been quite difficult to obtain by repeated summation. Here we argue that, in fact, P_{6}^{(10)}(n) can be obtained by repeated summation using the generalized Akiyama-Tanigawa algorithm described in equations (23) and (24). Of course this entails a lot of work since one has to construct 17 tables of coefficients c_{k,m}^{r}, r = 1, 2, …, 17, and, for each of these tables, one has to determine, starting from (24) and by repeated application of (23), the pair of elements c_{5,10}^{r} and c_{5,11}^{r}. Once the values of c_{5,10}^{r} and c_{5,11}^{r} have been ascertained for each r, a last application of (23) would allow us to obtain the desired coefficients c_{6,10}^{r}.

Fortunately, 382 years after the time of publication of Academia Algebrae, we can routinely run a modern computer to perform the calculations in a fraction of a second. Furthermore, besides relations (23) and (24), we can alternatively use the formulas (6) and (7) to directly evaluate the coefficients we want to. So, putting k = 6 and m = 10 in (6) and (7) yields

c_{6,10}^{r} = ∑_{i=max\{1,r−11\}}^{6} \frac{i!}{(i + 11)!} (∑_{t=1}^{i+11}(−1)^{i+11−t}|s(i + 11, t)|\binom{t}{r}11^{t−r})S(6, i).

By means of, for example, a computer algebra system such as Mathematica, we can readily compute this expression for r = 1, 2, …, 17. Next we quote the results as follows:

c_{6,10}^{1} = −96598656000/C,  c_{6,10}^{2} = −203020963200/C,
c_{6,10}^{3} = 90994289760/C,  c_{6,10}^{4} = 709177112512/C,
c_{6,10}^{5} = 1021675563656/C,  c_{6,10}^{6} = 812536224500/C,
c_{6,10}^{7} = 423402217056/C,  c_{6,10}^{8} = 155027658357/C,
c_{6,10}^{9} = 41338556974/C,  c_{6,10}^{10} = 8177397800/C,
c_{6,10}^{11} = 1208226448/C,  c_{6,10}^{12} = 132902770/C,
c_{6,10}^{13} = 10728564/C,  c_{6,10}^{14} = 617100/C,
c_{6,10}^{15} = 23936/C,  c_{6,10}^{16} = 561/C,
c_{6,10}^{17} = 6/C,

where C = 17!/5! = 2964061900800, in accordance with (9). We note that ∑_{r=1}^{17} c_{6,10}^{r} = 1. This is an instance of the general relation

∑_{r=1}^{k+m+1} c_{k,m}^{r} = 1,

which follows from the fact that P_{k}^{(m)}(1) = 1 for all k ≥ 0 and m ≥ 0.

7 Acknowledgement

The author would like to thank the anonymous referee for essential comments and suggesting Proposition 3.

References

[1] S. Akiyama and Y. Tanigawa, Multiple zeta values at non-positive integers, Ramanujan J. 5 (2001), 327–351.

[2] M. Kaneko, The Akiyama-Tanigawa algorithm for Bernoulli numbers, J. Integer Seq. 3 (2000), Article 00.2.9.

[3] K.-W. Chen, Algorithms for Bernoulli and Euler numbers, J. Integer Seq. 4 (2001), Article 01.1.6.

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

[5] T. C. T. Kotiah, Sums of powers of integers—A review, Int. J. Math. Educ. Sci. Technol. 24 (1993), 863–874.

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

   at http://oeis.org, 2012.

[7] T. J. Pfaff, Deriving a formula for sums of powers of integers, Pi Mu Epsilon J. 12 (2007), 425–430.

[8] H. Sherwood, Sums of power of integers and Bernoulli numbers, Math. Gaz. 54 (1970), 272–274.

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

2010 Mathematics Subject Classification: Primary 11Y55; Secondary 05A10. Keywords: hypersums of powers of integers, Akiyama-Tanigawa algorithm, Stirling number, Bernoulli number, harmonic number.

(Concerned with sequences \underline{A008275} and \underline{A008277}.)

Received November 12 2012; revised version received February 11 2013. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.