%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % "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)&=&\sum_{m=0}^ \infty (m+1)(a_{n-1,m}-a_{n-1,m+1})t^m\\ &=& \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})\\ &=& \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)). \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}&=&\sum_{m=0}^n \subs{n}{m}(-1)^m m!(a_{0,m-1}-a_{0,m})\\ &=& \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}\\ &=&-\sum_{m=0}^{n} (-1)^{m} m! a_{0,m}\left((m+1)\subs{n}{m+1}+ \subs{n}{m}\right)\\ &=&-\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*} &&\sum_{n=0}^\infty \left(\sum_{m=0}^n \frac{(-1)^mm!\subs{n+1}{m+1}}{m+1}\right) \frac{x^n}{n!}\\ &=& \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!}\\ &=&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}\\ &=& \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}