\input amstex
\documentstyle{amsppt}
\magnification=1100
\TagsOnRight
\input psfig

\newcount\refno
\define\beginreflist{\let\endreflist=!\refno=0
         \assignrefnumber}
\define\assignrefnumber#1{\ifx#1\endreflist\let\next=\relax
         \else\advance\refno by 1
         \edef#1{\the\refno}\let\next=\assignrefnumber
         \fi\next}

\beginreflist
\Abramowitz
\Graham
\Grassl
\Kaneko
\endreflist

\document
\centerline{\psfig{file=logo116.eps,width=4in}}
\vskip .3in
\centerline{\bf Algorithms for Bernoulli numbers and Euler numbers}
\vskip .3in
\centerline{Kwang-Wu Chen}
\vskip .2in
\centerline{Department of Accounting and Statistics}
\vskip .0in
\centerline{Dahan Institute of Technology}
\vskip .0in
\centerline{P. O. Box 4-27, Hua-Lian 971, Taiwan, Republic of China}
\vskip .2in
\centerline{Email address: kwchen\@ms01.dahan.edu.tw}

\vskip .5in
\centerline{\bf Abstract}
\vskip .2in
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.

\vskip .2in
1991 {\it Mathematics Subject Classification}. Primary 11B68
\vskip .1in
{\bf Keywords.}  Bernoulli number, Euler number, Euler polynomial, Stirling number of the second kind, tangent number

 
%=====================================================================================


\head 1. Introduction\endhead

Recently M. Kaneko (ref. \cite\Kaneko)\ reformulated Akiyama and Tanigawa's 
algorithm for computing Bernoulli numbers as follows:

\proclaim{\bf Proposition 1 (ref. \cite\Kaneko)}
Given an initial sequence $a_{0,m}$ ($m=0,1,2,\cdots$), define sequences
$a_{n,m}$ ($n\geq 1$) recursively by 
$$
  a_{n,m}=(m+1)\cdot (a_{n-1,m}-a_{n-1,m+1})\qquad (n\geq 1, m\geq 0).
$$
Then the leading elements
are given by
$$
  a_{n,0}=\sum^n_{m=0}(-1)^m m!{n+1 \brace m+1}a_{0,m},\tag 1
$$
where the Stirling numbers of the second kind ${n \brace m}$ are defined by
$$
  \frac{(e^x-1)^m}{m!}=\sum_{n=m}^\infty{n\brace m}\frac{x^n}{n!}.
$$
\endproclaim

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$, $\cdots$ 
The recursive rule gives the 
first row $1\cdot (1-1/2)$, $2\cdot (1/2-1/3)$, $3\cdot (1/3-1/4)$, 
$4\cdot (1/4-1/5)$, $\cdots$
which is $1/2$, $1/3$, $1/4$, $1/5$, $\cdots$. 
The 2nd row is given by $1\cdot (1/2-1/3)$,
$2\cdot (1/3-1/4)$, $3\cdot (1/4-1/5)$, $\cdots$, etc. 
The Akiyama-Tanigawa matrix $a_{n,m}$ is then
\vskip +.1in
\settabs 11\columns \+1 & 1/2 & 1/3 & 1/4 & 1/5 & 1/6 & 1/7 & 1/8 & 1/9 & 1/10 & 1/11 & ...\cr 
\+1/2 & 1/3 & 1/4 & 1/5 & 1/6 & 1/7 & 1/8 & 1/9 & 1/10 & 1/11 & ... \cr   
\+1/6 & 1/6 & 3/20 & 2/15 & 5/42 & 3/28 & 7/72 & 4/45 & 9/110 & ... \cr
\+0 & 1/30 & 1/20 & 2/35 & 5/84 & 5/84 & 7/120 & 28/495 & ... \cr
\+$-$1/30 & $-$1/30 & $-$3/140 & $-$1/105 & 0 & 1/140 & 49/3960 & ... \cr
\+0 & $-$1/42 & $-$1/28 & $-$4/105 & $-$1/28 & $-$29/924 & ... \cr
\+1/42 & 1/42 & 1/140 & $-$1/105 & $-$5/231 & ...  \cr
\+0 & 1/30 & 1/20 & 8/165 & ...  \cr
\+$-$1/30 & $-$1/30 & 1/220 & ...  \cr
\+0 & $-$5/66 & ... \cr
\+5/66 & ... \cr
\+... \cr
\vskip +.1in

M. Kaneko \cite\Kaneko\ 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}=\sum^\infty_{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\cdot a_{n-1,m}-(m+1)\cdot a_{n-1,m+1} \qquad (n\geq 1,m\geq 0).
$$
\proclaim{\bf Proposition 2}
Given an initial sequence $a_{0,m}$ $(m=0,1,2,\cdots)$, define the 
sequences $a_{n,m}$ $(n\geq 1)$ recursively by 
$$
  a_{n,m}=m\cdot a_{n-1,m}-(m+1)\cdot a_{n-1,m+1}, \qquad (n\geq 1,m\geq 0).\tag 2
$$
Then
$$
  a_{n,0}=\sum^n_{m=0}(-1)^m m!{n \brace m}a_{0,m}.\tag 3
$$
\endproclaim
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 \cite\Graham)
$$
  a_{n,0}=\sum^n_{m=0}\frac{(-1)^mm!{n \brace m}}{m+1}=B_n=B_n(0).
$$

In fact, we have the following theorem:
\proclaim{\bf Theorem 1}
Suppose the
initial sequence $a_{0,m}$ $(m=0,1,2,\cdots)$
has the ordinary generating function 
$$
  A(x)=\sum^\infty_{m=0}a_{0,m}x^m.
$$
Then the leading elements $a_{n,0}$ $(n=0,1,2, \ldots )$ have
exponential generating function
$$
  B(x)=\sum^\infty_{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.
\endproclaim

Consider now the
initial sequence $a_{0,m}=1/2^m$
in the A-algorithm and B-algorithm, 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}=\sum^\infty_{n=0}\frac{E_n(x)t^n}{n!}.
$$
Note that the Euler numbers $E_n$ can be defined as $2^nE_n(1/2)$. Alternatively we may
define the Euler numbers by
$$
  \sec x=\sum^\infty_{n=0}\frac{(-1)^nE_{2n}}{(2n)!}x^{2n}.
$$
They are closely related to the tangent numbers $T_n$ (cf. \cite\Grassl),
which are defined by
$$
  \tan x=\sum^\infty_{n=0}\frac{(-1)^{n+1}T_{2n+1}}{(2n+1)!}x^{2n+1},
  \qquad T_0=1.
$$

Moreover, if we take the initial sequence to be
$$
  a_{0,m}=(-1)^{[m/4]}\cdot 2^{-[m/2]}\cdot (1-\delta_{4,m+1}),
  \qquad\text{where }\delta_{4,i}=\cases 1,&\text{if}\quad 4|i,\\
                                        0,&\text{otherwise.}\endcases
$$
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.

\vskip 0.8cm
\head 2. Proof of Proposition 2 and Theorem 1\endhead

To prove Proposition 2, we use a similar trick 
to that used in the proof of Proposition 2 in \cite\Kaneko. Put 
$$
  g_n(t)=\sum^\infty_{m=0}a_{n,m}t^m.
$$
By the recursion Eq.(2) we have for $n\geq 1$
$$
\align
  g_n(t) &= \sum^\infty_{m=0}(m\cdot a_{n-1,m}-(m+1)\cdot a_{n-1,m+1})t^m \\
  &= \sum^\infty_{m=0}(m+1)a_{n-1,m+1}t^{m+1}-\sum^\infty_{m=0}(m+1)a_{n-1,m+1}t^m \\
  &= (t-1)\sum^\infty_{m=0}(m+1)a_{n-1,m+1}t^m \\
  &= (t-1)\frac d{dt}g_{n-1}(t) \ =\ \left((t-1)\frac d{dt}\right)^ng_0(t).
\endalign
$$
Using the recursion for the Stirling numbers of second kind
$$
  {n+1 \brace m+1}=(m+1){n \brace m+1}+{n \brace m},
$$
and mathematical induction on $n$, we have (ref. p.~310 in \cite\Graham)
$$
  \left((t-1)\frac d{dt}\right)^n = \sum^n_{m=0}{n \brace m}(t-1)^m
  \left(\frac d{dt}\right)^m.
$$
Therefore
$$
  g_n(t) = \sum^n_{m=0}{n \brace m}(t-1)^m\left(\frac d{dt}\right)^mg_0(t).
$$
Setting $t=0$ we get the assertion of Proposition 2
$$
  a_{n,0} = \sum^n_{m=0}{n \brace m}(-1)^mm!a_{0,m}.\qed
$$ 

Now we give the proof of Theorem 1.
In the A-algorithm 
we use the identity which appeared in Eq. (3) of \cite\Kaneko:
$$
  \frac{e^x(e^x-1)^m}{m!}=\sum^\infty_{n=m}{n+1 \brace m+1}\frac{x^n}{n!},
$$
and Eq.(1). Then the exponential generating function 
for the leading elements $a_{n,0}$ is
$$
\align
  B(x) = \sum^\infty_{n=0}a_{n,0}\frac{x^n}{n!} 
  &=\sum^\infty_{n=0}\left(\sum^n_{m=0}(-1)^mm!{n+1 \brace m+1}a_{0,m}\right)
       \frac{x^n}{n!} \\
  &= \sum^\infty_{m=0}(-1)^mm!a_{0,m}
                         \sum^\infty_{n=m}{n+1 \brace m+1}\frac{x^n}{n!} \\
  &= \sum^\infty_{m=0}(-1)^mm!a_{0,m}\frac{e^x(e^x-1)^m}{m!} \\
  &= e^x\sum^\infty_{m=0}(1-e^x)^ma_{0,m}\ =\ e^xA(1-e^x).
\endalign
$$

Next we treat the B-algorithm case.
Using Eq.(3) we have
$$
\align
  B(x) = \sum^\infty_{n=0} a_{n,0}\frac{x^n}{n!} 
  &= \sum^\infty_{n=0}\left(\sum^n_{m=0}(-1)^mm!{n \brace m}a_{0,m}\right)
           \frac{x^n}{n!} \\
        &= \sum^\infty_{m=0}(-1)^mm!a_{0,m}\sum^\infty_{n=m}{n \brace m}\frac{x^n}{n!} \\
  &= \sum^\infty_{m=0}(-1)^mm!a_{0,m}\frac{(e^x-1)^m}{m!} \\
  &= \sum^\infty_{m=0}(1-e^x)^ma_{0,m}\ =\ A(1-e^x).
\endalign
$$
This completes the proof of Theorem 1.\qed

%====================================================================================
\vskip 0.8cm
\head 3. Euler numbers and Tangent numbers\endhead

\proclaim{\bf Theorem 2}
Set $a_{0,m}=1/2^m$ for $m\geq 0$ in the A-algorithm and B-algorithm.
Then the leading elements $a_{n,0}$ for $n\geq 0$ are given by $E_n(1)$ 
and $E_n(0)$, respectively.
\endproclaim
\demo{Proof}
In the B-algorithm,
$$
\align
  A(1-e^x) &= \sum^\infty_{m=0}(1-e^x)^ma_{0,m} \\
           &= \sum^\infty_{m=0}\left(\frac{1-e^x}2\right)^m\ =\ \frac2{e^x+1}.
\endalign
$$
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. \qed
\enddemo

\proclaim{\bf Theorem 3}
Set 
$$
  a_{0,m}=(-1)^{[m/4]}\cdot 2^{-[m/2]}\cdot (1-\delta_{4,m+1}),
  \qquad\text{where }\delta_{4,i}=\cases 1,&\text{if}\quad 4|i,\\
                                        0,&\text{otherwise,}\endcases
$$
in the A-algorithm and B-algorithm.
Then
the leading elements $a_{n,0}$ are $E_n$ and $T_n$, respectively.
\endproclaim
\demo{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
$$
\align
  A(1-e^x) &= \sum^\infty_{m=0}(1-e^x)^ma_{0,m} \\
  &= \sum^\infty_{k=0}\frac{(-1)^k(1-e^x)^{4k}}{2^{2k}}+
              \sum^\infty_{k=0}\frac{(-1)^k(1-e^x)^{4k+1}}{2^{2k}}+
              \sum^\infty_{k=0}\frac{(-1)^k(1-e^x)^{4k+2}}{2^{2k+1}}. 
\endalign
$$
Let 
$$
  D(x)=\sum^\infty_{k=0}\frac{(-1)^k(1-e^x)^{4k}}{2^{2k}}
      =\frac 4{(e^{2x}-4e^x+5)(e^{2x}+1)}.
$$
Then
$$
\align
  A(1-e^x) &= D(x)+(1-e^x)D(x)+\frac{(1-e^x)^2}{2}D(x) \\
  &= D(x)\cdot (1+1-e^x+\frac{1-2e^x+e^{2x}}{2}) \\
  &= \frac 4{(e^{2x}-4e^x+5)(e^{2x}+1)}\cdot \frac{e^{2x}-4e^x+5}{2} 
  \ =\ \frac{2}{e^{2x}+1}.
\endalign
$$
This completes the proof.\qed
\enddemo

\noindent The following is the matrix generated by Theorem 3 for the Euler numbers $E_n$:
\vskip +.1in
\settabs 12\columns \+1 & 1 & 1/2 & 0 & -1/4 & -1/4 & -1/8 & 0 & 1/16 & 1/16 & 1/32 & ...\cr    
\+0 & 1 & 3/2 & 1 & 0 & -3/4 & -7/8 & -1/2 & 0 & 5/16 & ...\cr  
\+-1 & -1 & 3/2 & 4 & 15/4 & 3/4 & -21/8 & -4 & -45/16 & ...\cr
\+0 & -5 & -15/2 & 1 & 15 & 81/4 & 77/8 & -19/2 & ...\cr 
\+5 & 5 & -51/2 & -56 & -105/4 & 255/4 & 1071/8 & ...\cr
\+0 & 61 & 183/2 & -119 & -450 & -1683/4 & ...\cr
\+-61 & -61 & 1263/2 & 1324 & -585/4 & ...\cr
\+0 & -1385 & -4155/2 & 5881 & ...\cr  
\+1385 & 1385 & -47751/2 & ...\cr
\+0 & 50521 & ...\cr
\+-50521 & ...\cr  
\+...\cr
\vskip +.1in

\noindent The following is the matrix generated by Theorem 3 for the tangent numbers $T_n$:
\vskip +.1in
\settabs 13\columns \+1 & 1 & 1/2 & 0 & -1/4 & -1/4 & -1/8 & 0 
& 1/16 & 1/16 & 1/32 & 0 & ...\cr  
\+-1 & 0 & 1 & 1 & 1/4 & -1/2 & -3/4 & -1/2 & -1/16 & 1/4 & 5/16 & ...\cr
\+0 & -2 & -1 & 2 & 7/2 & 2 & -1 & -3  & -11/4 & -7/8 & ...\cr
\+2 & 0 & -8 & -8 & 4 & 16 & 15 & 1 & -113/8 & ...\cr 
\+0 & 16 & 8 & -40 & -64 & -10 & 83 & 120 & ...\cr  
\+-16 & 0 & 136 & 136 & -206 & -548 & -342 & ...\cr 
\+0 & -272 & -136 & 1232 & 1916 & -688 & ...\cr   
\+272 & 0 & -3968 & -3968 & 11104 & ...\cr
\+0 & 7936 & 3968 & -56320 & ...\cr 
\+-7936 & 0 & 176896 & ...\cr
\+0 & -353792 & ...\cr
\+353792 & ...\cr
\+...\cr
\vskip +.1in

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$.
\proclaim{\bf Corollary}
$$
\aligned
  E_n(0) &= \sum^n_{m=0}\frac{(-1)^mm!{n \brace m}}{2^m},\\
  E_n(1) &= \sum^n_{m=0}\frac{(-1)^mm!{n+1 \brace m+1}}{2^m},\qquad
\endaligned
\aligned
  E_n    &= \sum^n_{m=0}(-1)^m m!{n+1 \brace m+1}a_{0,m},\\
  T_n    &= \sum^n_{m=0}(-1)^mm!{n \brace m}a_{0,m},
\endaligned
$$
where $\{a_{0,m}\}^\infty_{m=0}$ is the initial sequence in Theorem 3.
\endproclaim

\proclaim{\bf Remark}
{\rm 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)=\sum^\infty_{m=0}\frac{(e^x-1)^m}{m!}=e^{e^x-1}.
$$
}
\endproclaim

\proclaim{Acknowledgements}
{\rm 
I would like to thank the referee for some useful comments and suggestions.
}
\endproclaim

%===================================================================================

\Refs
\widestnumber\no{10}

\ref
\no \Abramowitz
\by M. Abramowitz and I. A. Stegun
\book Handbook of mathematical functions 
      with formulas, graphs, and mathematical tables
\publ Dover Publications, Inc., New York
\yr 1972
\endref

\ref
\no \Graham
\by R. Graham, D. Knuth, and O. Patashnik
\book Concrete Mathematics
\publ Addison-Wesley
\yr 1989
\endref

\ref
\no \Grassl
\by R. M. Grassl
\paper Euler numbers and skew-hooks
\jour Math. Mag.
\yr 1993
\vol 66
\pages 181--188
\issue 3
\endref

\ref
\no \Kaneko
\by M. Kaneko
\paper The Akiyama-Tanigawa algorithm for Bernoulli numbers
\jour Journal of Integer Sequences
\vol 3
\yr 2000
\pages 1--6
\paperinfo Article 00.2.9
\endref

\endRefs

\bigskip
\hrule

\medskip
\noindent
(Mentions sequences A000110, A000182, A000364, A027641, A027642.)

\medskip
\hrule

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

\medskip
\hrule


\enddocument