<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% "The Akiyama-Tanigawa algorithm for Bernoulli numbers"
%    by Masanobu Kaneko
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article}

\usepackage{color}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\usepackage{psfig,epsf}
\usepackage{amsmath,amssymb}


\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}



\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\newcommand{\subs}[2]{{{#1}\brace{#2}}} \newcommand{\Z}{{\mathbf Z}}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo29.eps}
\vskip 1cm

{\LARGE \bf The Akiyama-Tanigawa algorithm for Bernoulli numbers} 
\vskip 1.5cm

{\large Masanobu Kaneko} \smallskip \\
Graduate School of Mathematics \\
Kyushu University \\
Fukuoka 812-8581, Japan \medskip \\
Email address: \href{mailto:mkaneko@math.kyushu-u.ac.jp}{mkaneko@math.kyushu-u.ac.jp} \\
\vskip2.5cm
{\bf Abstract}
\end{center}
{\em 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.}

\section{The Algorithm} 
In their study of values at non-positive integer arguments of multiple
zeta functions, S. Akiyama and Y. Tanigawa \cite{AT} 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,\,\frac12,\,\frac13,\,\frac14,\,\frac15,\dots$ and define the first
row by $1\cdot(1-\frac12),\,2\cdot(\frac12-\frac13),\,
3\cdot(\frac13-\frac14),\dots$ which produces the sequence $\frac12,
\frac13, \frac14,\dots.$ Then define the next row by
$1\cdot(\frac12-\frac13),\,2\cdot(\frac13-\frac14),\,
3\cdot(\frac14-\frac15),\dots,$ thus giving $\frac16, \frac16,
\frac{3}{20}, \dots$ as the second row.
In general, denoting the
$m$-th ( $m=0,1,2,\dots$) number in the $n$-th ($n=0,1,2,\dots$) 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)\cdot(a_{n,m}-a_{n,m+1}).
\label{rec}
$$
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
$$
\sum_{n=0}^\infty B_n \frac{x^n}{n!}=\frac{xe^x}{e^x-1}\left(
  =\frac{x}{e^{x}-1}+x\right).
$$
Note that we are using
the definition of the Bernoulli numbers in which
$B_1=\frac12$.
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
$\zeta(1-k)=-B_k/k \ (k=1,2,3,\dots)$ for the values of the Riemann
zeta  function.

\vspace{10mm}

\begin{figure}[htb]
\setlength{\unitlength}{1mm}
\begin{picture}(120,110)(0,-60)

\put(1,51.5){\circle{6}}
\put(0,50){$1$}
\put(15,50){$\frac12$}
\put(30,50){$\frac13$}
\put(45,50){$\frac14$}
\put(60,50){$\frac15$}
\put(75,50){$\frac16$}
\put(90,50){$\frac17$}
\put(105,50){$\frac18$}
\put(120,50){$\frac19\quad\cdots$}
%
\multiput(3,47)(15,0){8}{\vector(2,-3){4}}
\multiput(14,47)(15,0){8}{\vector(-2,-3){4}}
%
\put(8.7,38.1){\circle{6}}
\put(7.5,37){$\frac12$}
\put(22.5,37){$\frac13$}
\put(37.5,37){$\frac14$}
\put(52.5,37){$\frac15$}
\put(67.5,37){$\frac16$}
\put(82.5,37){$\frac17$}
\put(97.5,37){$\frac18$}
\put(112.5,37){$\frac19\quad\cdots$}
%
\multiput(10.5,34)(15,0){7}{\vector(2,-3){4}}
\multiput(21.5,34)(15,0){7}{\vector(-2,-3){4}}
%
\put(16.2,25.1){\circle{6}}
\put(15,24){$\frac16$}
\put(30,24){$\frac16$}
\put(45,24){$\frac3{20}$}
\put(60,24){$\frac2{15}$}
\put(75,24){$\frac5{42}$}
\put(90,24){$\frac3{28}$}
\put(105,24){$\frac7{72}\quad\cdots$}
%
\multiput(18,21)(15,0){6}{\vector(2,-3){4}}
\multiput(29,21)(15,0){6}{\vector(-2,-3){4}}
%
\put(23.5,12.5){\circle{6}}
\put(22.5,11){$0$}
\put(37.5,11){$\frac1{30}$}
\put(52.5,11){$\frac1{20}$}
\put(67.5,11){$\frac2{35}$}
\put(82.5,11){$\frac5{84}$}
\put(97.5,11){$\frac5{84}\quad\cdots$}
%
\multiput(25.5,8)(15,0){5}{\vector(2,-3){4}}
\multiput(36.5,8)(15,0){5}{\vector(-2,-3){4}}
%
\put(31,-0.8){\circle{7}}
\put(26,-2){$-\frac1{30}$}
\put(41,-2){$-\frac1{30}$}
\put(56,-2){$-\frac3{140}$}
\put(70,-2){$-\frac{1}{105}$}
\put(90,-2){$0\quad\cdots$}
%
\multiput(33,-5)(15,0){4}{\vector(2,-3){4}}
\multiput(44,-5)(15,0){4}{\vector(-2,-3){4}}
%
\put(38.7,-13.3){\circle{6}}
\put(37.5,-15){$0$}
\put(48.5,-15){$-\frac{1}{42}$}
\put(63.5,-15){$-\frac{1}{28}$}
\put(77.5,-15){$-\frac{4}{105}\quad\cdots$}
%
\multiput(40.5,-18)(15,0){3}{\vector(2,-3){4}}
\multiput(51.5,-18)(15,0){3}{\vector(-2,-3){4}}
%
\put(46.7,-26.8){\circle{6}}
\put(45,-28){$\frac{1}{42}$}
\put(60,-28){$\frac{1}{42}$}
\put(75,-28){$\frac{1}{140}\quad\cdots$}
%
\multiput(48,-31)(15,0){2}{\vector(2,-3){4}}
\multiput(59,-31)(15,0){2}{\vector(-2,-3){4}}
%
\put(53.5,-39.5){\circle{6}}
\put(52.5,-41){$0$}
\put(67,-41){$\frac{1}{30}\quad\cdots$}
%
\put(55.5,-44){\vector(2,-3){4}}
\put(66.5,-44){\vector(-2,-3){4}}
%
\put(60.3,-52.8){\circle{7}}
\put(56,-54){$-\frac{1}{30}\quad\cdots$}
\end{picture} 
\caption{Akiyama-Tanigawa triangle}
\end{figure}


\section{Proof}
The proof is based on the following identity for Bernoulli numbers, a
variant of which goes as far back as Kronecker (see \cite{G}). Here we
denote by $\subs{n}{m}$ the Stirling number of the  second kind:
$$
x^n=\sum_{m=0}^n \subs{n}{m} x^{{\underline m}},
$$
where $x^{{\underline m}}=x(x-1)\cdots (x-m+1)$ for $m\ge1$ and
$x^{{\underline 0}}=1$. (We use Knuth's notation \cite{Kn}.  For the
Stirling number identities that  we shall need, the reader is referred
for example to  \cite{GKP}.)

\begin{theorem}
  $$
  B_n = \sum_{m=0}^{n} \frac{ (-1)^m m ! \subs{n+1}{m+1} }{m+1}
  ,\qquad \forall n \geq 0.
$$
\end{theorem}

\noindent  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.

\begin{proposition}
  Given an initial sequence  $a_{0,m}\ (m=0,1,2,\dots)$, define the
  sequences $a_{n,m}\ (n\ge1)$ recursively by
\begin{equation}
  a_{n,m}=(m+1)\cdot(a_{n-1,m}-a_{n-1,m+1})\quad (n\ge1, m\ge0).
\label{rec2}
\end{equation}
Then
\begin{equation}
  a_{n,0}=\sum_{m=0}^n (-1)^mm!\subs{n+1}{m+1}a_{0,m}.
\label{propformula}
\end{equation}
\end{proposition}

\noindent {\it Proof.} \, Put
$$
g_n(t)=\sum_{m=0}^ \infty a_{n,m}t^m.
$$
By the recursion (\ref{rec2}) we have for $n\ge1$
\begin{eqnarray*}
  g_{n}(t)&amp;=&amp;\sum_{m=0}^ \infty (m+1)(a_{n-1,m}-a_{n-1,m+1})t^m\\
  &amp;=&amp; \frac{d}{dt}(\sum_{m=0}^ \infty a_{n-1,m} t^{m+1})-
\frac{d}{dt}(\sum_{m=0}^ \infty a_{n-1,m+1} t^{m+1})\\
&amp;=&amp; \frac{d}{dt}(tg_{n-1}(t))-\frac{d}{dt}(g_{n-1}(t)-a_{n-1,0})\\
&amp;=&amp; g_{n-1}(t)+(t-1)\frac{d}{dt}(g_{n-1}(t))\\
&amp;=&amp; \frac{d}{dt}((t-1)g_{n-1}(t)).
\end{eqnarray*}
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))\quad (n\ge 1),
$$
and thus
$$
h_n(t)=\left((t-1)\frac{d}{dt}\right)^n(h_0(t)).
$$
Applying the formula ({\it cf.} \cite[Ch. 6.7 Exer. 13]{GKP})
$$
\left(x\frac{d}{dx}\right)^n=\sum_{m=0}^n\subs{n}{m}x^m\left(
\frac{d}{dx}\right)^m
$$
for $x=t-1$, we have
$$
h_n(t)=\sum_{m=0}^n \subs{n}{m}(t-1)^m \left(\frac{d}{dt}
\right)^m h_0(t).
$$
Putting $t=0$ we obtain
\begin{eqnarray*}
  -a_{n,0}&amp;=&amp;\sum_{m=0}^n \subs{n}{m}(-1)^m m!(a_{0,m-1}-a_{0,m})\\
&amp;=&amp; \sum_{m=0}^{n-1} \subs{n}{m+1} (-1)^{m+1}(m+1)! a_{0,m}
-\sum_{m=0}^{n} \subs{n}{m} (-1)^{m}m! a_{0,m}\\
&amp;=&amp;-\sum_{m=0}^{n}  (-1)^{m} m! a_{0,m}\left((m+1)\subs{n}{m+1}+
\subs{n}{m}\right)\\
&amp;=&amp;-\sum_{m=0}^{n}  (-1)^{m} m!\subs{n+1}{m+1}a_{0,m}.
\end{eqnarray*}
(We have used the recursion
$\subs{n+1}{m+1}=(m+1)\subs{n}{m+1}+\subs{n}{m}$.)
This proves the proposition.\\

\noindent {\it 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
\begin{equation}
\frac{e^x(e^x-1)^m}{m!}=\sum_{n=m}^\infty \subs{n+1}{m+1} \frac{x^n}{n!}
\label{stirgen}
\end{equation}
which results from the well-known generating series for the Stirling
numbers ({\it cf.} \cite[(7.49)]{GKP})
$$
\frac{(e^x-1)^m}{m!}=\sum_{n=m}^\infty \subs{n}{m} \frac{x^n}{n!} 
$$
by replacing $m$ with $m+1$ and differentiating with respect to $x$.
With this, we have
\begin{eqnarray*}
&amp;&amp;\sum_{n=0}^\infty \left(\sum_{m=0}^n 
\frac{(-1)^mm!\subs{n+1}{m+1}}{m+1}\right) \frac{x^n}{n!}\\
&amp;=&amp;
\sum_{m=0}^\infty \frac{(-1)^mm!}{m+1} \sum_{n=m}
^\infty \subs{n+1}{m+1} \frac{x^n}{n!}
=\sum_{m=0}^\infty \frac{(-1)^mm!}{m+1}\frac{e^x(e^x-1)^m}{m!}\\
&amp;=&amp;e^x \sum_{m=0}^\infty \frac{(1-e^x)^m}{m+1}
= \frac{e^x}{1-e^x} \sum_{m=1}^\infty \frac{(1-e^x)^m}{m}\\
&amp;=&amp; \frac{e^x}{1-e^x} \left(-\log \left(1-(1-e^x)\right)\right)
=\frac{xe^x}{e^x-1}.
\end{eqnarray*}
This proves Theorem 1.

\paragraph{Remark.}
A referee suggested the following interpretation of the algorithm
using generating function:

Suppose the first row is $a_0, a_1, a_2, \dots,$ with ordinary
generating function
$$
A(x)=\sum_{n=0}^\infty a_n x^n.
$$
Let the leading diagonal be $b_0=a_0, b_1, b_2,\dots,$ with
exponential generating function
$$
{\mathbb B}(x)=\sum_{n=0}^\infty b_n \frac{x^n}{n!}.
$$

Then we have
$$
{\mathbb B}(x)=e^x A(1-e^x).
$$
This follows from \eqref{propformula} and \eqref{stirgen}, the
calculation being parallel to that of the proof of Theorem 1.  To get
the Bernoulli numbers we take $a_0=1, a_1=\frac12, a_2=\frac13,\dots$
with $A(x)=-\log(1-x)/x$, and find ${\mathbb B}(x)=xe^x/(e^x-1)$.

\section{Poly-Bernoulli numbers}
If we replace the initial sequence $1,\frac12, \frac13, \frac14,
\dots$ by $1,\frac1{2^k}, \frac1{3^k}, \frac1{4^k}, \dots$ and apply
the same algorithm, the resulting sequence is $(-1)^n D_n^{(k)}\ (
n=0,1,2,\dots)$, where $D_n^{(k)}$ is a variant of ``poly-Bernoulli
numbers'' (\cite{Ka}, \cite{AK1}, \cite{AK2}): For any integer $k$, we
define a sequence of numbers $D_n^{(k)}$ by
$$
\frac{Li_k(1-e^{-x})}{e^x-1}=\sum_{n=0}^\infty D_n^{(k)}\frac{x^n}{n!},
$$
where $Li_k(t)=\sum_{m=1}^\infty \frac{t^m}{m^k}$ ($k$-th
polylogarithm when $k\ge 1$). The above assertion is then a
consequence of the  following (or, is just a special case of the
preceding remark)

\begin{proposition} For any $k\in \Z$ and $n\ge0$, we have
$$
 D_n^{(k)}=(-1)^n \sum_{m=0}^n \frac{(-1)^mm!\subs{n+1}{m+1}}{(m+1)^k}.
 $$
\end{proposition}

\noindent {\it 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.

\section*{Acknowledgements}
I should like to thank the referee for several comments and suggestions.

\begin{thebibliography}{20}

\bibitem{AT} Akiyama, S. and Tanigawa, Y. : Multiple zeta values at
  non-positive integers, {\em preprint} (1999).  
  
\bibitem{AK1} Arakawa, T. and Kaneko, M. : Multiple zeta values,
  poly-Bernoulli numbers, and related zeta functions, {\em Nagoya
    Math. J.} {\bf 153} (1999), 189--209.  
  
\bibitem{AK2} Arakawa, T. and Kaneko, M. : On poly-Bernoulli  numbers,
  {\em Comment. Math. Univ. Sanct. Pauli} {\bf 48-2} (1999), 159--167.
  
\bibitem{G} Gould, H. G. : Explicit formulas for Bernoulli numbers,
  {\em Amer. Math. Monthly} {\bf 79} (1972), 44--51.  
  
\bibitem{GKP} Graham, R., Knuth, D. and Patashnik, O.: Concrete
  Mathematics, Addison-Wesley, (1989).  
  
\bibitem{Ka} Kaneko, M. : Poly-Bernoulli numbers,  {\em
    Jour. Th. Nombre Bordeaux} {\bf 9} (1997), 199--206.  
  
\bibitem{Kn} Knuth, D. : Two notes on notation, {\em Amer. Math.
    Monthly} {\bf 99} (1992), 403--422.  

\end{thebibliography}

\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}

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

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Received August 7, 2000;
published in Journal of Integer Sequences December 12, 2000.

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home
page}{https://cs.uwaterloo.ca/journals/JIS/}.


\centerline{\rule{6.5in}{.01in}}


\end{document}

</pre></body></html>