Algorithms for Bernoulli numbers and Euler numbers

Kwang-Wu Chen

Department of Accounting and Statistics Dahan Institute of Technology P. O. Box 4-27, Hua-Lian 971, Taiwan, Republic of China

Email address: kwchen@ms01.dahan.edu.tw

Abstract

In this paper we investigate some algorithms which produce Bernoulli numbers, Euler numbers, and tangent numbers. We also give closed formulae for Euler numbers and tangent numbers in terms of Stirling numbers of the second kind.

1991 Mathematics Subject Classification. Primary 11B68

Keywords. Bernoulli number, Euler number, Euler polynomial, Stirling number of the second kind, tangent number

1. Introduction

Recently M. Kaneko (ref. [4]) reformulated Akiyama and Tanigawa’s algorithm for computing Bernoulli numbers as follows:

Proposition 1 (ref. [4]). Given an initial sequence a_{0,m} (m = 0, 1, 2, ⋯), define 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).

Then the leading elements are given by

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

where the Stirling numbers of the second kind \left\{{n \atop m}\right\} are defined by

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

Typeset by AMS-TEX

Suppose the initial sequence is a_{0,m} = 1/(m + 1). Then the Akiyama and Tanigawa algorithm is the following. Begin with the 0-th row 1, 1/2, 1/3, 1/4, 1/5, 1/6, ⋯ The recursive rule gives the first row 1 · (1 − 1/2), 2 · (1/2 − 1/3), 3 · (1/3 − 1/4), 4 · (1/4 − 1/5), ⋯ which is 1/2, 1/3, 1/4, 1/5, · · ·. The 2nd row is given by 1·(1/2−1/3), 2·(1/3−1/4), 3·(1/4−1/5), ⋯, etc. The Akiyama-Tanigawa matrix a_{n,m} is then

1  1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9 1/10 1/11 ...
1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9 1/10 1/11 ...
1/6 1/6 3/20 2/15 5/42 3/28 7/72 4/45 9/110 ...
0  1/30 1/20 2/35 5/84 5/84 7/120 28/495 ...
−1/30 −1/30 −3/140−1/1050  1/140 49/3960...
0  −1/42 −1/28 −4/105−1/28 −29/924 ...
1/42 1/42 1/140 −1/105−5/231...
0  1/30 1/20 8/165 ...
−1/30 −1/30 1/220 ...
0  −5/66 ...
5/66 ...

...

M. Kaneko [4] gave a direct proof that the leading element a_{n,0} in the above array is B_{n}(1), where the Bernoulli polynomials B_{n}(x) are defined by

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

Note that Bernoulli numbers B_{n} can be defined as B_{n}(0).

In the sequel we denote the above algorithm as the A-algorithm. Let us change the recursive step in the A-algorithm to

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

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 · a_{n−1,m} − (m + 1) · a_{n−1,m+1},  (n ≥ 1, m ≥ 0).  (2)

Then

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

We call the algorithm in Proposition 2 the B-algorithm. If we again start with the initial sequence a_{0,m} = 1/(m + 1), then (cf. Eq. (6.99) or p. 560 of [2])

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

In fact, we have the following theorem:

Theorem 1. Suppose the initial sequence a_{0,m} (m = 0, 1, 2, ⋯) has the ordinary generating function

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

Then the leading elements a_{n,0} (n = 0, 1, 2, …) have exponential generating function

B(x) = ∑_{n=0}^{∞} a_{n,0} \frac{x^{n}}{n!}

given by e^{x}A(1 − e^{x}) for the A-algorithm and A(1 − e^{x}) for the B-algorithm.

Consider now the initial sequence a_{0,m} = 1/2^{m} in the A-algorithm and Balgorithm, respectively. We obtain the leading elements a_{n,0} as E_{n}(1) and E_{n}(0), respectively, where the Euler polynomials E_{n}(x) are defined by

\frac{2e^{xt}}{e^{t} + 1} = ∑_{n=0}^{∞} \frac{E_{n}(x)t^{n}}{n!} .

Note that the Euler numbers E_{n} can be defined as 2^{n}E_{n}(1/2). Alternatively we may define the Euler numbers by

sec x = ∑_{n=0}^{∞} \frac{(−1)^{n}E_{2n}}{(2n)!} x^{2n}.

They are closely related to the tangent numbers T_{n} (cf. [3]), which are defined by

tan x = ∑_{n=0}^{∞} \frac{(−1)^{n+1}T_{2n+1}}{(2n + 1)!} x^{2n+1}, T_{0} = 1.

Moreover, if we take the initial sequence to be

a_{0,m} = (−1)^{[m/4]} · 2^{−[m/2]} · (1 − δ_{4,m+1}), where δ_{4,i} = \{ \begin{matrix}1, & if 4|i, \\ 0, & otherwise. \end{matrix}

in the A-algorithm and B-algorithm, respectively, the leading elements a_{n,0} become E_{n} and T_{n}, respectively. We now give the proof of the above statements.

2. Proof of Proposition 2 and Theorem 1

To prove Proposition 2, we use a similar trick to that used in the proof of Proposition 2 in [4]. Put

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

By the recursion Eq.(2) we have for n ≥ 1

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

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

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

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

Using the recursion for the Stirling numbers of second kind

\left\{{n + 1 \atop m + 1}\right\} = (m + 1)\left\{{n \atop m + 1}\right\} + \left\{{n \atop m}\right\},

and mathematical induction on n, we have (ref. p. 310 in [2])

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

Therefore

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

Setting t = 0 we get the assertion of Proposition 2

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

Now we give the proof of Theorem 1. In the A-algorithm we use the identity which appeared in Eq. (3) of [4]:

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

and Eq.(1). Then the exponential generating function for the leading elements a_{n,0} is

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

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

= ∑_{m=0}^{∞}(−1)^{m}m!a_{0,m} \frac{e^{x}(e^{x} − 1)^{m}}{m!}

= e^{x} ∑_{m=0}^{∞}(1 − e^{x})^{m}a_{0,m} = e^{x}A(1 − e^{x}).

Next we treat the B-algorithm case. Using Eq.(3) we have

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

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

= ∑_{m=0}^{∞}(−1)^{m}m!a_{0,m} \frac{(e^{x} − 1)^{m}}{m!}

= ∑_{m=0}^{∞}(1 − e^{x})^{m}a_{0,m} = A(1 − e^{x}).

This completes the proof of Theorem 1. □

3. Euler numbers and Tangent numbers

Theorem 2. Set a_{0,m} = 1/2^{m} for m ≥ 0 in the A-algorithm and B-algorithm. Then the leading elements a_{n,0} for n ≥ 0 are given by E_{n}(1) and E_{n}(0), respectively.

Proof. In the B-algorithm,

A(1 − e^{x}) = ∑_{m=0}^{∞}(1 − e^{x})^{m}a_{0,m}

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

The exponential generating functions for E_{n}(0) and E_{n}(1) are 2/(e^{x} + 1) and 2e^{x}/(e^{x} + 1), respectively. Using Theorem 1 completes the proof. □

Theorem 3. Set

a_{0,m} = (−1)^{[m/4]} · 2^{−[m/2]} · (1 − δ_{4,m+1}), where δ_{4,i} = \{ \begin{matrix}1, & if 4|i, \\ 0, & otherwise, \end{matrix}

in the A-algorithm and B-algorithm. Then the leading elements a_{n,0} are E_{n} and T_{n}, respectively.

Proof. The exponential generating functions for E_{n} and T_{n} are 2e^{x}/(e^{2x} + 1) and 2/(e^{2x} + 1), respectively. From the results of Theorem 1, we only need to prove that A(1 − e^{x}) = 2/(e^{2x} + 1) in the B-algorithm. We have

A(1 − e^{x}) = ∑_{m=0}^{∞}(1 − e^{x})^{m}a_{0,m}

= ∑_{k=0}^{∞} \frac{(−1)^{k}(1 − e^{x})^{4k}}{2^{2k}} + ∑_{k=0}^{∞} \frac{(−1)^{k}(1 − e^{x})^{4k+1}}{2^{2k}} + ∑_{k=0}^{∞} \frac{(−1)^{k}(1 − e^{x})^{4k+2}}{2^{2k+1}} .

Let

D(x) = ∑_{k=0}^{∞} \frac{(−1)^{k}(1 − e^{x})^{4k}}{2^{2k}} = \frac{4}{(e^{2x} − 4e^{x} + 5)(e^{2x} + 1)}.

Then

A(1 − e^{x}) = D(x) + (1 − e^{x})D(x) + \frac{(1 − e^{x})^{2}}{2} D(x)

= D(x) · (1 + 1 − e^{x} + \frac{1 − 2e^{x} + e^{2x}}{2} )

= \frac{4}{(e^{2x} − 4e^{x} + 5)(e^{2x} + 1)} · \frac{e^{2x} − 4e^{x} + 5}{2} = \frac{2}{e^{2x} + 1}.

This completes the proof. □ The following is the matrix generated by Theorem 3 for the Euler numbers E_{n}:

1  1  1/2 0  -1/4 -1/4 -1/8 0  1/16 1/16 1/32 ...
0  1  3/2 1  0  -3/4 -7/8 -1/2 0  5/16 ...
-1  -1  3/2 4  15/4 3/4 -21/8 -4  -45/16 ...
0  -5  -15/2 1  15 81/4 77/8 -19/2 ...
5  5  -51/2 -56 -105/4 255/4 1071/8...
0  61 183/2 -119 -450 -1683/4...
-61 -61 1263/21324 -585/4 ...
0  -1385 -4155/25881 ...
1385 1385 -47751/2 ...
0  50521 ...
-50521 ...

... The following is the matrix generated by Theorem 3 for the tangent numbers T_{n}:

1  1  1/2 0  -1/4 -1/4 -1/8 0  1/16 1/16 1/32 0  ...
-1 0  1  1  1/4 -1/2 -3/4 -1/2 -1/16 1/4 5/16 ...
0  -2 -1 2  7/2 2  -1 -3 -11/4 -7/8 ...
2  0  -8 -8 4  16 15 1  -113/8...
0  16 8  -40 -64 -10 83 120 ...
-16 0  136 136 -206 -548 -342 ...
0  -272 -136 1232 1916 -688 ...
272 0  -3968 -3968 11104 ...
0  7936 3968 -56320...
-7936 0  176896...
0  -353792 ...

353792... ...

Using Eq.(1) and Eq.(3) in Theorem 2 and 3, we can give closed formulae for E_{n}(0), E_{n}(1), E_{n}, and T_{n}.

Corollary.

\begin{aligned}E_{n}(0) & = ∑_{m=0}^{n} \frac{(−1)^{m}m!\left\{{n \atop m}\right\}}{2^{m}}, \\ E_{n}(1) & = ∑_{m=0}^{n} \frac{(−1)^{m}m!\left\{{n+1 \atop m+1}\right\}}{2^{m}}, \end{aligned}  \begin{aligned}E_{n} & = ∑_{m=0}^{n}(−1)^{m}m!\left\{{n + 1 \atop m + 1}\right\}a_{0,m}, \\ T_{n} & = ∑_{m=0}^{n}(−1)^{m}m!\left\{{n \atop m}\right\}a_{0,m}, \end{aligned}

where {a_{0,m}}_{m=0}^{∞} is the initial sequence in Theorem 3.

Remark. A referee mentions that the B-algorithm may well yield other notable sequences. For instance, the Bell numbers can be obtained from the initial sequence (−1)^{n}/n!, since their exponential generating function is

B(x) = A(1 − e^{x}) = ∑_{m=0}^{∞} \frac{(e^{x} − 1)^{m}}{m!} = e^{e^{x}−1}.

Acknowledgements. I would like to thank the referee for some useful comments and suggestions.

References

1. M. Abramowitz and I. A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables, Dover Publications, Inc., New York, 1972.

2. R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

3. R. M. Grassl, Euler numbers and skew-hooks, Math. Mag. 66 (1993), no. 3, 181–188.

4. M. Kaneko, The Akiyama-Tanigawa algorithm for Bernoulli numbers, Article 00.2.9, Journal of Integer Sequences 3 (2000), 1–6.

(Mentions sequences A000110, A000182, A000364, A027641, A027642.)

Received April 12, 2001; revised version received May 15, 2001. Published in Journal of Integer Sequences, July 13, 2001.