The Akiyama-Tanigawa algorithm for Bernoulli numbers

Masanobu Kaneko

Graduate School of Mathematics Kyushu University Fukuoka 812-8581, Japan

Email address: mkaneko@math.kyushu-u.ac.jp

Abstract

A direct proof is given for Akiyama and Tanigawa’s algorithm for computing Bernoulli numbers. The proof uses a closed formula for Bernoulli numbers expressed in terms of Stirling numbers. The outcome of the same algorithm with different initial values is also briefly discussed.

1 The Algorithm

In their study of values at non-positive integer arguments of multiple zeta functions, S. Akiyama and Y. Tanigawa [1] found as a special case an amusing algorithm for computing Bernoulli numbers in a manner similar to “Pascal’s triangle” for binomial coefficients.

Their algorithm reads as follows: Start with the 0-th row 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, … and define the first row by 1·(1− \frac{1}{2}), 2·(\frac{1}{2} − \frac{1}{3}), 3·(\frac{1}{3} − \frac{1}{4}), … which produces the sequence \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, …. Then define the next row by 1·(\frac{1}{2} − \frac{1}{3}), 2·(\frac{1}{3} − \frac{1}{4}), 3· (\frac{1}{4} − \frac{1}{5}), …, thus giving \frac{1}{6}, \frac{1}{6}, \frac{3}{20}, … as the second row. In general, denoting the m-th ( m = 0, 1, 2, …) number in the n-th (n = 0, 1, 2, …) row by a_{n,m}, the m-th number in the (n + 1)-st row a_{n+1,m} is determined recursively by

a_{n+1,m} = (m + 1) · (a_{n,m} − a_{n,m+1}).

Then the claim is that the 0-th component a_{n,0} of each row (the “leading diagonal”) is just the n-th Bernoulli numbers B_{n}, where

∑_{n=0}^{∞} B_{n} \frac{x^{n}}{n!} = \frac{xe^{x}}{e^{x} − 1} (= \frac{x}{e^{x} − 1} + x) .

Note that we are using the definition of the Bernoulli numbers in which B_{1} = \frac{1}{2}. This is the definition used by Bernoulli (and independently Seki, published one year prior to Bernoulli). Incidentally, this is more appropriate for the Euler formula ζ(1 − k) = −B_{k}/k (k = 1, 2, 3, …) for the values of the Riemann zeta function.

2 Proof

The proof is based on the following identity for Bernoulli numbers, a variant of which goes as far back as Kronecker (see [4]). Here we denote by \left\{{n \atop m}\right\} the Stirling number of the second kind:

x^{n} = ∑_{m=0}^{n} \left\{{n \atop m}\right\}x\underline{m},

where x\underline{m} = x(x − 1) ⋯ (x − m + 1) for m ≥ 1 and x\underline{0} = 1. (We use Knuth’s notation [7]. For the Stirling number identities that we shall need, the reader is referred for example to [5].)

Theorem 1

B_{n} = ∑_{m=0}^{n} \frac{(−1)^{m}m!\left\{{n+1 \atop m+1}\right\}}{m + 1}, ∀n ≥ 0.

We shall give later a proof of this identity for the sake of completeness. Once we have this, the next proposition ensures the validity of our algorithm.

[figure: 1; \frac{1}{2}; \frac{1}{3}; \frac{1}{4}; \frac{1}{5}; \frac{1}{6}; \frac{1}{7}; \frac{1}{8}; ^{^{\frac{1}{9}} ⋯}; \frac{1}{2}; \frac{1}{3}; \frac{1}{4}; \frac{1}{5}; \frac{1}{6}; \frac{1}{7}; \frac{1}{8}; ^{^{\frac{1}{9}} ⋯}; \frac{1}{6}; \frac{1}{6}; \frac{3}{20}; \frac{2}{15}; \frac{5}{42}; \frac{3}{28}; ^{^{\frac{7}{72}} ⋯}; 0; \frac{1}{30}; \frac{1}{20}; \frac{2}{35}; \frac{5}{84}; ^{^{\frac{5}{84}} ⋯}; −\frac{1}{30}; −\frac{1}{30}; −\frac{3}{140}; −\frac{1}{105}; 0 ⋯; 0; −\frac{1}{42}; −\frac{1}{28}; −\frac{4}{105} ⋯; \frac{1}{42}; \frac{1}{42}; ^{^{\frac{1}{140}} ⋯}; 0; ^{^{\frac{1}{30}} ⋯}; −\frac{1}{30} ⋯]

Figure 1: Akiyama-Tanigawa triangle

Proposition 2 Given an initial sequence a_{0,m} (m = 0, 1, 2, …), define the sequences a_{n,m} (n ≥ 1) recursively by

a_{n,m} = (m + 1) · (a_{n−1,m} − a_{n−1,m+1}) (n ≥ 1, m ≥ 0).  (1)

Then

a_{n,0} = ∑_{m=0}^{n}(−1)^{m}m!\left\{{n + 1 \atop m + 1}\right\}a_{0,m}.  (2)

Proof. Put

g_{n}(t) = ∑_{m=0}^{∞} a_{n,m}t^{m}.

By the recursion (1) we have for n ≥ 1

g_{n}(t) = ∑_{m=0}^{∞}(m + 1)(a_{n−1,m} − a_{n−1,m+1})t^{m}

= \frac{d}{dt}(∑_{m=0}^{∞} a_{n−1,m}t^{m+1}) − \frac{d}{dt}(∑_{m=0}^{∞} a_{n−1,m+1}t^{m+1})
= \frac{d}{dt}(tg_{n−1}(t)) − \frac{d}{dt}(g_{n−1}(t) − a_{n−1,0})
= g_{n−1}(t) + (t − 1)\frac{d}{dt}(g_{n−1}(t))
= \frac{d}{dt}((t − 1)g_{n−1}(t)).

Hence, by putting (t − 1)g_{n}(t) = h_{n}(t) we obtain

h_{n}(t) = (t − 1)\frac{d}{dt}(h_{n−1}(t)) (n ≥ 1),

and thus

h_{n}(t) = ((t − 1)\frac{d}{dt})^{n} (h_{0}(t)).

Applying the formula (cf. [5, Ch. 6.7 Exer. 13])

(x\frac{d}{dx})^{n} = ∑_{m=0}^{n} \left\{{n \atop m}\right\}x^{m} (\frac{d}{dx})^{m}

for x = t − 1, we have

h_{n}(t) = ∑_{m=0}^{n} \left\{{n \atop m}\right\}(t − 1)^{m} (\frac{d}{dt})^{m} h_{0}(t).

Putting t = 0 we obtain

−a_{n,0} = ∑_{m=0}^{n} \left\{{n \atop m}\right\}(−1)^{m}m!(a_{0,m−1} − a_{0,m})

= ∑_{m=0}^{n−1} \left\{{n \atop m + 1}\right\}(−1)^{m+1}(m + 1)!a_{0,m} − ∑_{m=0}^{n} \left\{{n \atop m}\right\}(−1)^{m}m!a_{0,m}

= − ∑_{m=0}^{n}(−1)^{m}m!a_{0,m} ((m + 1)\left\{{n \atop m + 1}\right\} + \left\{{n \atop m}\right\})

= − ∑_{m=0}^{n}(−1)^{m}m!\left\{{n + 1 \atop m + 1}\right\}a_{0,m}.

(We have used the recursion \left\{{n+1 \atop m+1}\right\} = (m + 1)\left\{{n \atop m+1}\right\} + \left\{{n \atop m}\right\}.) This proves the proposition.

Proof of Theorem 1. We show the generating series of the right hand side coincide with that of B_{n}. To do this, we use the identity

\frac{e^{x}(e^{x} − 1)^{m}}{m!} = ∑_{n=m}^{∞} \left\{{n + 1 \atop m + 1}\right\}\frac{x^{n}}{n!}  (3)

which results from the well-known generating series for the Stirling numbers (cf. [5, (7.49)])

\frac{(e^{x} − 1)^{m}}{m!} = ∑_{n=m}^{∞} \left\{{n \atop m}\right\}\frac{x^{n}}{n!}

by replacing m with m + 1 and differentiating with respect to x. With this, we have

∑_{n=0}^{∞} (∑_{m=0}^{n} \frac{(−1)^{m}m!\left\{{n+1 \atop m+1}\right\}}{m + 1}) \frac{x^{n}}{n!}

= ∑_{m=0}^{∞} \frac{(−1)^{m}m!}{m + 1} ∑_{n=m}^{∞} \left\{{n + 1 \atop m + 1}\right\}\frac{x^{n}}{n!} = ∑_{m=0}^{∞} \frac{(−1)^{m}m!}{m + 1} \frac{e^{x}(e^{x} − 1)^{m}}{m!}

= e^{x} ∑_{m=0}^{∞} \frac{(1 − e^{x})^{m}}{m + 1} = \frac{e^{x}}{1 − e^{x}} ∑_{m=1}^{∞} \frac{(1 − e^{x})^{m}}{m}
= \frac{e^{x}}{1 − e^{x}} (− log (1 − (1 − e^{x}))) = \frac{xe^{x}}{e^{x} − 1}.

This proves Theorem 1.

Remark. A referee suggested the following interpretation of the algorithm using generating function:

Suppose the first row is a_{0}, a_{1}, a_{2}, …, with ordinary generating function

A(x) = ∑_{n=0}^{∞} a_{n}x^{n}.

Let the leading diagonal be b_{0} = a_{0}, b_{1}, b_{2}, …, with exponential generating function

𝔹(x) = ∑_{n=0}^{∞} b_{n} \frac{x^{n}}{n!} .

Then we have

𝔹(x) = e^{x}A(1 − e^{x}).

This follows from (2) and (3), the calculation being parallel to that of the proof of Theorem 1. To get the Bernoulli numbers we take a_{0} = 1, a_{1} = \frac{1}{2}, a_{2} = \frac{1}{3}, … with A(x) = − log(1 − x)/x, and find 𝔹(x) = xe^{x}/(e^{x} − 1).

3 Poly-Bernoulli numbers

If we replace the initial sequence 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, … by 1, \frac{1}{2^{k}} , \frac{1}{3^{k}} , \frac{1}{4^{k}} , … and apply the same algorithm, the resulting sequence is (−1)^{n}D_{n}^{(k)} (n = 0, 1, 2, …), where D_{n}^{(k)} is a variant of “poly-Bernoulli numbers” ([6], [2], [3]): For any integer k, we define a sequence of numbers D_{n}^{(k)} by

\frac{Li_{k}(1 − e^{−x})}{e^{x} − 1} = ∑_{n=0}^{∞} D_{n}^{(k)} \frac{x^{n}}{n!} ,

where Li_{k}(t) = ∑_{m=1}^{∞} \frac{t^{m}}{m^{k}} (k-th polylogarithm when k ≥ 1). The above assertion is then a consequence of the following (or, is just a special case of the preceding remark)

Proposition 3 For any k ∈ Z and n ≥ 0, we have

D_{n}^{(k)} = (−1)^{n} ∑_{m=0}^{n} \frac{(−1)^{m}m!\left\{{n+1 \atop m+1}\right\}}{(m + 1)^{k}}.

Proof. The proof can be given completely in the same way as the proof of Theorem 1 using generating series, and hence will be omitted.

Acknowledgements

I should like to thank the referee for several comments and suggestions.

References

[1] Akiyama, S. and Tanigawa, Y. : Multiple zeta values at non-positive integers, preprint (1999).

[2] Arakawa, T. and Kaneko, M. : Multiple zeta values, poly-Bernoulli numbers, and related zeta functions, Nagoya Math. J. 153 (1999), 189– 209.

[3] Arakawa, T. and Kaneko, M. : On poly-Bernoulli numbers, Comment. Math. Univ. Sanct. Pauli 48-2 (1999), 159–167.

[4] Gould, H. G. : Explicit formulas for Bernoulli numbers, Amer. Math. Monthly 79 (1972), 44–51.

[5] Graham, R., Knuth, D. and Patashnik, O.: Concrete Mathematics, Addison-Wesley, (1989).

[6] Kaneko, M. : Poly-Bernoulli numbers, Jour. Th. Nombre Bordeaux 9 (1997), 199–206.

[7] Knuth, D. : Two notes on notation, Amer. Math. Monthly 99 (1992), 403–422.

(The Bernoulli numbers are \underline{A027641} and \underline{A027642}. The table in Figure 1 yields sequences \underline{A051714} and \underline{A051715}. Other sequences which mention this paper are \underline{A000367}, \underline{A002445}, \underline{A026741}, \underline{A045896}, \underline{A051712}, \underline{A051713}, \underline{A051716}, \underline{A051717}, \underline{A051718}, \underline{A051719}, \underline{A051720}, \underline{A051721}, \underline{A051722}, and \underline{A051723}.

Received August 7, 2000; published in Journal of Integer Sequences December 12, 2000.

Return to Journal of Integer Sequences home page. 8