\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Algorithms for Bernoulli and \\ \vskip .1in Related Polynomials} \vskip 1cm \large Ayhan Dil, Veli Kurt and Mehmet Cenkci\\ Department of Mathematics \\ Akdeniz University\\ Antalya, 07058 \\ Turkey\\ \href{mailto:adil@akdeniz.edu.tr}{\tt adil@akdeniz.edu.tr}\\ \href{mailto:vkurt@akdeniz.edu.tr}{\tt vkurt@akdeniz.edu.tr}\\ \href{mailto:cenkci@akdeniz.edu.tr}{\tt cenkci@akdeniz.edu.tr} \end{center} \vskip .3in \begin{abstract} We investigate some algorithms that produce Bernoulli, Euler and Genocchi polynomials. We also give closed formulas for Bernoulli, Euler and Genocchi polynomials in terms of weighted Stirling numbers of the second kind, which are extensions of known formulas for Bernoulli, Euler and Genocchi numbers involving Stirling numbers of the second kind. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{definition}{Definition}[section] \section{Introduction and Primary Concepts} Bernoulli numbers $B_{n}$, $n\in \mathbb{Z}$, $n\geqslant 0$, originally arise in the study of finite sums of a given power of consecutive integers. They are given by $B_{0}=1$, $B_{1}=-1/2$, $B_{2}=1/6$, $% B_{4}=-1/30,\ldots $, with $B_{n}=0$ for odd $n>1$, and% \begin{equation*} B_{n}=-\frac{1}{n+1}\sum_{m=0}^{n-1}\binom{n+1}{m}B_{m} \end{equation*}% \noindent for all even $n\geqslant 2$. In the symbolic notation, Bernoulli numbers are given recursively by% \begin{equation*} \left( B+1\right) ^{n}-B_{n}=\left\{ \begin{array}{ll} 1, & \text{if }n=1; \\ 0, & \text{if }n>1.% \end{array}% \right. \end{equation*}% \noindent with the usual convention about replacing $B^{j}$ by $B_{j}$ after expansion. The Bernoulli polynomials $B_{n}\left( x\right) $, $n\in \mathbb{Z% }$, $n\geqslant 0$, can be expressed in the form% \begin{equation} B_{n}\left( x\right) =\left( B+x\right) ^{n}=\sum_{m=0}^{n}\binom{n}{m}% B_{m}x^{n-m}. \label{EK2} \end{equation} The generating functions of Bernoulli numbers and polynomials are respectively given by% \begin{equation*} \frac{t}{e^{t}-1}=\sum_{n=0}^{\infty }B_{n}\frac{t^{n}}{n!}, \end{equation*}% \noindent and% \begin{equation*} \frac{te^{xt}}{e^{t}-1}=\sum_{n=0}^{\infty }B_{n}\left( x\right) \frac{t^{n}% }{n!}, \end{equation*}% \noindent for $|t|<2\pi $ (\cite{Apostol}). The Euler polynomials $% E_{n}\left( x\right) $, $n\in \mathbb{Z}$, $n\geqslant 0$, may be defined by the generating function \cite{N1,N} \begin{equation} \frac{2e^{xt}}{e^{t}+1}=\sum_{n=0}^{\infty }E_{n}\left( x\right) \frac{t^{n}% }{n!}, \label{2.b} \end{equation}% \noindent for $|t|<\pi $. The Euler numbers $E_{n}$ are defined by% \begin{equation*} E_{n}=2^{n}E_{n}\left( \frac{1}{2}\right) \text{, }n\geqslant 0. \end{equation*}% \noindent The Genocchi numbers and polynomials, $G_{n}$ and $G_{n}\left( x\right) $, $n\in \mathbb{Z}$, $n\geqslant 0$, are defined respectively as follows \cite[p.49]{Com}: \begin{equation} \frac{2t}{e^{t}+1}=\sum_{n=0}^{\infty }G_{n}\frac{t^{n}}{n!}, \label{3.a} \end{equation}% \noindent and% \begin{equation*} \frac{2te^{xt}}{e^{t}+1}=\sum_{n=0}^{\infty }G_{n}\left( x\right) \frac{t^{n}% }{n!}, \end{equation*}% \noindent for $|t|<\pi $, which have several combinatorial interpretations in terms of certain surjective maps of finite sets \cite{D1,DV,DuR}. The well-known identity \begin{equation*} G_{n}=2\left( 1-2^{n}\right) B_{n}\text{, }n\geqslant 0, \end{equation*}% \noindent shows the relation between Genocchi and Bernoulli numbers. From (% \ref{2.b}) and (\ref{3.a}), it is easy to see that% \begin{equation*} G_{n}=nE_{n-1}\left( 0\right) \text{, }n\geqslant 0, \end{equation*} \noindent with $E_{-1}:=0$. Several arithmetical properties of Bernoulli, Euler and Genocchi polynomials can be obtained from the generating functions. We list here three of them, which will be used in the next section.% \begin{eqnarray} B_{n}\left( 1+x\right) &=&B_{n}\left( x\right) +nx^{n-1}\text{, }n\geqslant 0, \label{4} \\ E_{n}\left( 1+x\right) &=&-E_{n}\left( x\right) +2x^{n}\text{, }n\geqslant 0, \label{5} \\ G_{n}\left( 1+x\right) &=&-G_{n}\left( x\right) +2nx^{n-1}\text{, }% n\geqslant 0. \label{6} \end{eqnarray} Bernoulli, Euler and Genocchi numbers can be directly computed from generating functions by dividing numerator to denominator (after expanding $% e^{t}$) and comparing the coefficients on either sides. Besides this method, many recurrence formulas for Bernoulli, Euler and Genocchi numbers are obtained \cite{CCK,CH,Com,DR,H1,J,K1,M}. Alternative methods for computing these numbers are developed as well. In this paper, we concern two of them, the Euler-Seidel matrices and the Akiyama-Tanigawa algorithm. \begin{definition} \label{def1}(\cite{D2}) Let $a_{0}$, $a_{1}$, $a_{2}$,$\ldots $,$a_{n}$,$% \ldots $ be an initial sequence. The Euler-Seidel matrix corresponding to the sequence $\left\{ a_{n}\right\} $ is determined by the sequence $\left\{ a_{n}^{k}\right\} $, whose elements are recursively given by% \begin{eqnarray} a_{n}^{0} &=&a_{n}\text{ \ \ \ \ }\left( n\geqslant 0\right) , \notag \\ a_{n}^{k} &=&a_{n}^{k-1}+a_{n+1}^{k-1}\text{ \ \ \ \ }\left( n\geqslant 0,k\geqslant 1\right) . \label{7} \end{eqnarray} \end{definition} \noindent The sequence $\left\{ a_{n}^{0}\right\} $ is the first row and the sequence $\left\{ a_{0}^{k}\right\} $ is the first column of the matrix. From the recurrence relation (\ref{7}), it can be seen that% \begin{equation} a_{n}^{k}=\sum_{i=0}^{k}\binom{k}{i}a_{n+i}^{0}\text{, }\left( n\geqslant 0,k\geqslant 1\right) . \label{8} \end{equation}% \noindent The first row and column can be determined from (\ref{8}) as follows:% \begin{eqnarray} a_{0}^{n} &=&\sum_{i=0}^{n}\binom{n}{i}a_{i}^{0}\text{, }n\geqslant 0, \notag \\ a_{n}^{0} &=&\sum_{i=0}^{n}\binom{n}{i}\left( -1\right) ^{n-i}a_{0}^{i}\text{% , }n\geqslant 0. \label{9} \end{eqnarray}% \noindent Thus, as the first row is given, the first column can be found and vice versa. Next two propositions show the relationship between the generating functions of $a_{n}^{0}$ and $a_{0}^{n}$. \begin{proposition} \label{prop1}Let% \begin{equation*} a\left( t\right) =\sum_{n=0}^{\infty }a_{n}^{0}t^{n} \end{equation*}% \noindent be the generating function of the initial sequence $\left\{ a_{n}^{0}\right\} $. Then the generating function of the sequence $\left\{ a_{0}^{n}\right\} $ is given by% \begin{equation*} \overline{a}\left( t\right) =\sum_{n=0}^{\infty }a_{0}^{n}t^{n}=\frac{1}{1-t}% a\left( \frac{t}{1-t}\right) . \end{equation*} \end{proposition} \noindent The proof of this proposition is given by Euler \cite{E}. \begin{proposition} \label{prop2}Let% \begin{equation*} A\left( t\right) =\sum_{n=0}^{\infty }a_{n}^{0}\frac{t^{n}}{n!} \end{equation*}% \noindent be the exponential generating function of the initial sequence $% \left\{ a_{n}^{0}\right\} $. Then the exponential generating function of the sequence $\left\{ a_{0}^{n}\right\} $ is given by% \begin{equation*} \overline{A}\left( t\right) =\sum_{n=0}^{\infty }a_{0}^{n}\frac{t^{n}}{n!}% =e^{t}A\left( t\right) . \end{equation*} \end{proposition} \noindent The proof of this proposition is given by Seidel \cite{S}. Of notable interest of Euler-Seidel matrices is the examples for Bernoulli and related numbers. Let% \begin{equation*} A\left( t\right) =\frac{t}{e^{t}-1}. \end{equation*}% \noindent Then% \begin{equation*} \overline{A}\left( t\right) =\frac{te^{t}}{e^{t}-1}=t+\frac{t}{e^{t}-1}, \end{equation*}% \noindent and thus% \begin{equation*} \overline{A}\left( t\right) =t+A\left( t\right) . \end{equation*}% \noindent Therefore,% \begin{equation*} a_{0}^{0}=B_{0}=1\text{, }a_{0}^{1}=\frac{1}{2}\text{, and }% a_{n}^{0}=a_{0}^{n}\text{ for }n\geqslant 2, \end{equation*}% \noindent and the corresponding Euler-Seidel matrix is% \begin{equation*} \left( \begin{array}{cccccc} 1 & -\frac{1}{2} & \frac{1}{6} & 0 & -\frac{1}{30} & \cdots \\ \frac{1}{2} & -\frac{1}{3} & \frac{1}{6} & -\frac{1}{30} & \cdots & \\ \frac{1}{6} & -\frac{1}{6} & \frac{2}{15} & \cdots & & \\ 0 & -\frac{1}{30} & \cdots & & & \\ -\frac{1}{30} & \cdots & & & & \\ \cdots & & & & & \end{array}% \right) \end{equation*} For% \begin{equation*} A\left( t\right) =\frac{2t}{e^{t}+1}, \end{equation*}% \noindent the initial sequence is% \begin{equation*} a_{0}^{0}=0\text{, }a_{1}^{0}=1\text{, }a_{2n+1}^{0}=0\text{ and }% a_{2n}^{0}=G_{2n}\text{ for }n\geqslant 1. \end{equation*}% \noindent Since% \begin{equation*} \overline{A}\left( t\right) =\frac{2te^{t}}{e^{t}+1}=2t-\frac{2t}{e^{t}+1}% =2t-A\left( t\right) , \end{equation*}% \noindent it is seen that% \begin{equation*} a_{0}^{0}=0\text{, }a_{0}^{1}=1\text{, }a_{0}^{2n+1}=0\text{ and }% a_{0}^{2n}=-G_{2n}\text{ for }n\geqslant 1. \end{equation*}% \noindent Thus, the corresponding Euler-Seidel matrix is% \begin{equation*} \left( \begin{array}{cccccccccc} 0 & 1 & -1 & 0 & 1 & 0 & -3 & 0 & 17 & \cdots \\ 1 & 0 & -1 & 1 & 1 & -3 & -3 & 17 & \cdots & \\ 1 & -1 & 0 & 2 & -2 & -6 & 14 & \cdots & & \\ 0 & -1 & 2 & 0 & -8 & 8 & \cdots & & & \\ -1 & 1 & 2 & -8 & 0 & \cdots & & & & \\ 0 & 3 & -6 & -8 & \cdots & & & & & \\ 3 & -3 & -14 & \cdots & & & & & & \\ 0 & -17 & \cdots & & & & & & & \\ -17 & \cdots & & & & & & & & \\ \cdots & & & & & & & & & \end{array}% \right) \end{equation*} In their study of values at nonpositive integer arguments of multiple zeta functions, Akiyama and Tanigawa \cite{AT} found an algorithm for computing Bernoulli numbers in a manner similar to Pascal's triangle for binomial coefficients. The algorithm is as follows: Starting with the sequence $% \left\{ 1/n\right\} $, $n\geqslant 1$, as the $0$-th row, the $m$-th number in the $\left( n+1\right) $-st row $a_{m}^{n+1}$ is determined recursively by% \begin{equation*} a_{m}^{n+1}=\left( m+1\right) \left( a_{m}^{n}-a_{m+1}^{n}\right) , \end{equation*}% \noindent for $m=0,1,2,\ldots $ and $n=0,1,2,\ldots $. Then, $a_{0}^{n}$ of each row is the $n$-th Bernoulli number $B_{n}$ with $B_{1}=1/2$. Kaneko \cite{K2} reformulated the Akiyama-Tanigawa algorithm as follows: \begin{proposition} \label{prop3}Given an initial sequence $a_{m}^{0}$ with $m=0,1,2,\ldots $ define sequence $a_{m}^{n}$ for $n\geqslant 1$ recursively by% \begin{equation*} a_{m}^{n}=\left( m+1\right) \left( a_{m}^{n-1}-a_{m+1}^{n-1}\right) . \end{equation*}% \noindent Then the leading elements are given by% \begin{equation*} a_{0}^{n}=\sum_{m=0}^{n}\left( -1\right) ^{m}m!S\left( n+1,m+1\right) a_{m}^{0}. \end{equation*} \end{proposition} \noindent Here, $S\left( n,m\right) $ denotes the Stirling numbers of the second kind which are defined as follows \cite[Chap.\ 5]{Com}: \begin{equation} \frac{\left( e^{t}-1\right) ^{m}}{m!}=\sum_{n=m}^{\infty }S\left( n,m\right) \frac{t^{n}}{n!}. \label{Ek3} \end{equation}% \noindent For $1\leqslant m\leqslant n$, $S\left( n,m\right) >0$ and for $% 1\leqslant n