TOPICS
Search

Akiyama-Tanigawa Algorithm


The Akiyama-Tanigawa algorithm is a triangular recurrence for computing Bernoulli numbers and transforming sequences (Kaneko 2000, Akiyama and Tanigawa 2001). Starting with

 a_(0,m)=1/(m+1),
(1)

define subsequent rows by

 a_(n+1,m)=(m+1)(a_(n,m)-a_(n,m+1))
(2)

for nonnegative integers n and m. The leading element of row n is

 a_(n,0)=B_n(1)=(-1)^nB_n,
(3)

where B_n(x) is a Bernoulli polynomial and B_n=B_n(0) uses the convention B_1=-1/2. Thus the algorithm gives a_(1,0)=1/2 and agrees with B_n at every other index (Kaneko 2000, Chen 2001).

More generally, an arbitrary initial row a_(0,m)=c_m gives

 a_(n,0)=sum_(m=0)^n(-1)^mm!S(n+1,m+1)c_m,
(4)

where S(n,m) is a Stirling number of the second kind. If the initial row has ordinary generating function A(t)=sum_(m=0)^(infty)c_mt^m, then the leading column has exponential generating function

 sum_(n=0)^inftya_(n,0)(t^n)/(n!)=e^tA(1-e^t).
(5)

These identities hold as formal power series (Kaneko 2000).

Chen's (2001) variation uses the same initial row and the recurrence

 b_(n+1,m)=mb_(n,m)-(m+1)b_(n,m+1).
(6)

Its leading column satisfies

b_(n,0)=sum_(m=0)^(n)(-1)^mm!S(n,m)c_m
(7)
sum_(n=0)^(infty)b_(n,0)(t^n)/(n!)=A(1-e^t).
(8)

In particular, c_m=1/(m+1) gives the conventional Bernoulli numbers b_(n,0)=B_n. The choice c_m=2^(-m) gives the Euler polynomial values E_n(1) under the original recurrence and E_n(0) under the variation. The choice c_m=(-1)^m/m! gives the Bell numbers with indices n+1 and n, respectively (Chen 2001).

The initial row with ordinary generating function

 A(t)=2/(t^2-2t+2)
(9)

gives the signed Euler numbers E_n under the original recurrence. Under the variation, the leading column has exponential generating function 1-tanht. Writing its entries as tau_n, the initial value is tau_0=1 and

tau_(2k)=0
(10)
tau_(2k-1)=(-1)^kT_k
(11)

for k>=1, where T_k is a tangent number in the positive convention T_1=1, T_2=2, T_3=16, ... (Chen 2001).

A two-parameter generalization replaces the recurrence by

 a_(n+1,m)=(m+1)(xa_(n,m)-ya_(n,m+1)).
(12)

For nonzero x and y, its leading-column exponential generating function is

 sum_(n=0)^inftya_(n,0)(t^n)/(n!)=e^(xt)A(y/x(1-e^(xt)))
(13)

(Rahmani 2013).


See also

Bernoulli Number, Euler Number, Euler Polynomial, Stirling Number of the Second Kind, Tangent Number

Explore with Wolfram|Alpha

References

Akiyama, S. and Tanigawa, Y. "Multiple Zeta Values at Non-Positive Integers." Ramanujan J. 5, 327-351, 2001. https://doi.org/10.1023/A:1013981102941.Chen, K.-W. "Algorithms for Bernoulli Numbers and Euler Numbers." J. Integer Sequences 4, Article 01.1.6, 2001. https://cs.uwaterloo.ca/journals/JIS/VOL4/CHEN/AlgBE2.html.Kaneko, M. "The Akiyama-Tanigawa Algorithm for Bernoulli Numbers." J. Integer Sequences 3, Article 00.2.9, 2000. https://cs.uwaterloo.ca/journals/JIS/VOL3/KANEKO/AT-kaneko.html.Rahmani, M. "The Akiyama-Tanigawa Matrix and Related Combinatorial Identities." Lin. Alg. Appl. 438, 219-230, 2013. https://doi.org/10.1016/j.laa.2012.07.050.

Cite this as:

Weisstein, Eric W. "Akiyama-Tanigawa Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Akiyama-TanigawaAlgorithm.html

Subject classifications