AsyRec: A Maple package for Computing the

Asymptotics of Solutions of Linear Recurrence Equations with Polynomial Coefficients

Doron ZEILBERGER^{1}

Better late than never. When Jet Wimp and I wrote the expository article:

J. Wimp and D. Zeilberger, Resurrecting the asymptotics of linear recurrences, J. Math. Anal. Appl. 111, 162-177 (1985),

I did not know much about computer algebra systems. Now that I do, I thought that it is about time to write a Maple implementation of the Birkhoff-Trjitzinsky method so lucidly described in that paper.

It is amazing how fast Maple, with the aid of this package, can compute asymptotics of solutions of linear recurrence equations with polynomial coefficients to any desired order. In particular, it can derive, very fast, the asymptotics for the number of involutions of size n, that probably took Moser and Wyman (Canadian J. Math. 7 (1955), 159-168) at least one month, and probably took Don Knuth (“The Art of Computing Programming”, v. 3, 5.1.4) several hours.

Just type: Asy(N**2-N-(n+1),n,N,10); ,

to get the asymptotics up to the 10^{th} order.

The Birkhoff-Trjitzinsky method suffers from one drawback. It only does the asymptotics up to a multiplicative constant C. But nowadays this is hardly a problem. Just crank-out the first ten thousand terms of the sequence using the very recurrence whose asymptotics you are trying to find, not forgetting to furnish the few necessary initial conditions, and then estimate the constant empirically. If you are lucky, then Maple can recognize it in terms of “famous” constants like e and π, by typing identify(C);.

For example, to get the asymptotics for the number of involutions of size n, just type:

a:= AsyC(N**2-N-(n+1),n,N,5,[1,2],10000); ,

and you would get, after a few seconds, the output:

0.55069531490320e^{−1/2 n}n^{1/2 n}e^{\sqrt{n}}·

(1 + \frac{7}{24} \frac{1}{\sqrt{n}} − \frac{119}{1152} n^{−1} − \frac{7933}{414720} n^{−3/2} + \frac{1967381}{39813120} n^{−2} − \frac{57200419}{1337720832} n^{−5/2}−

\frac{562799}{47775744} n^{−3} − \frac{526420847}{40131624960} n^{−7/2} + \frac{1856209}{573308928} n^{−4} − \frac{267645803}{2407897497600} n^{−9/2} + O(n^{−5}))

1 Supported in part by the USA National Science Foundation. Exclusively published in the Personal Journal of Ekhad

and Zeilberger: http://www.math.rutgers.edu/~zeilberg/pj.html . April 4, 2008.

Now in order to see what the constant in front might be, just use Maple’s identify, and type:

identify(0.55069531490320);

and you would immediately get (\sqrt{2}/2)e^{−1/4}, in complete agreement with Moser-Wyman and Knuth. Involutions are permutations all whose cycle-lengths are from the set {1, 2}. The procedure

OperPerG(N,n,S);

will find the linear recurrence operator annihilating the enumerating sequence for permutations whose cycle-lengths are all drawn from the set S, followed by the necessary initial values. For example

OperPerG(N,n,{1,2});

would give the operator N^{2} − N − (n + 1) discussed above. To get the asymptotics for the number of permutations π of n objects such that π^{r} equals the identity permutation, for r = 2, ….R, type:

SipurPerm(R,n,M,L);

where M is the desired order and L is the length of the sequence used to estimate the constant.

For example, try: SipurPerm(6,n,5,10000); .

For R > 6 Maple fails because of the complexity of the system of equations it has to solve. It is fun to use AsyRec in conjunction with the Zeilberger algorithm that is also included in the package. For example, for the asymptotics for the sum of r-th powers of the rows of Pascal’s triangle, for r from 2 to R , with the same meanings of M and L as before, try: SipurBin(R,n,M,L).

For example, try: SipurBin(6,n,4,10000); .
The webpage of this article: http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/asy.html

contains several sample input and output, as well as a link to the package, that can be also downloaded directly from

http://www.math.rutgers.edu/~zeilberg/tokhniot/ AsyRec .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: zeilberg at math dot rutgers dot edu . Website: http://www.math.rutgers.edu/~zeilberg/ .