%asy.tex:
%Title
%%a Plain TeX article by Doron Zeilberger (2 pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\N{{\cal N}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\R{{\cal R}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\def\Tilde{\char126\relax}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
AsyRec: A Maple package  for Computing the }
\centerline
{
Asymptotics of Solutions of Linear Recurrence Equations
with Polynomial Coefficients}                                           
\rm
\bigskip
\centerline 
{\it Doron ZEILBERGER\footnote{$^1$}
{\eightrm
Supported in part by the USA National Science Foundation.
Exclusively published in the Personal Journal of Ekhad and
Zeilberger:
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/pj.html}  .
April 4, 2008.
}
}

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

J. Wimp and D. Zeilberger,
{\it Resurrecting the asymptotics of linear
recurrences}, J. Math. Anal. Appl. {\bf 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 {\it 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 ({\it Canadian J. Math.}
{\bf 7} (1955), 159-168) at least one month,
and probably took Don Knuth ({\it ``The Art of Computing Programming''},
v. 3, 5.1.4) several hours.

Just type: {\tt 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 {\it multiplicative}
constant $C$. But {\bf 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 {\it initial conditions},
and then {\it estimate} the constant {\bf empirically}.
If you are lucky, then Maple can recognize it in terms of
``famous'' constants like $e$ and $\pi$, by typing
{\tt identify(C);}.

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

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

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

$$
0.55069531490320
{e^{-1/2\,n}}{n}^{1/2\,n}{e^{\sqrt {n}}} \cdot
$$
$$
( 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})
)
$$


Now in order to see what the constant in front might be,
just use Maple's {\tt identify}, and type:

{\tt 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 

{\tt 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

{\tt 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 $\pi$
of $n$ objects such that $\pi^r$ equals the identity permutation,
for $r=2, \dots. R$, type: 

{\tt SipurPerm(R,n,M,L);}

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

For example, try: {\tt 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 {\tt 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 {\tt M} and {\tt L} as before, 
try: {\tt SipurBin(R,n,M,L)}. For  example, try:
{\tt SipurBin(6,n,4,10000);} .


The webpage of this article: {\eighttt http://www.math.rutgers.edu/\Tilde 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

{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/
AsyRec}   .

\bigskip

{\bf Doron Zeilberger}, 
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
\hfill\break
Email: {\eighttt zeilberg at math dot rutgers dot edu} .
Website: {\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/} .
\end











