%appswz.tex:
%%a Plain TeX file by Moa Apagodu and Doron Zeilberger (8 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\P{{\cal P}}
\def\Tilde{\char126\relax}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\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
\centerline
{
\bf
FIVE Applications of Wilf-Zeilberger Theory to
Enumeration and Probability
\footnote{$^1$}
{\eightrm \raggedright
Oct. 18, 2006.
Accompanied by Maple packages {\eighttt AppsWZ} and
{\eighttt AppsWZmulti} downloadable from Zeilberger's website.
Sample input and output can be viewed in: \hfill\break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimhtml/
appswz.html} .
The research of the second author was supported in part by the NSF.
}
}
\bigskip
\centerline{Moa APAGODU and Doron ZEILBERGER}
\bigskip
\qquad\qquad\qquad\qquad\qquad\qquad\qquad
{\it Dedicated to Sergei Abramov on becoming {\bf FIVE}-dozen
years old}
{\bf Explicit Formulas vs. Algorithms}
In the old days, when one had to find some sequence, $a(n)$,
there were two extremes. In the lucky case, one had an
{\bf explicit formula}. For example, the probability
of tossing a fair coin $2n$ times and getting exactly $n$ Heads,
equals $(2n)!/(2^{2n} n!^2)$.
Sometimes, cheatingly,
one considered as `explicit' expressions in terms
of sums (or multisums) or integrals (or multi-integrals).
The other extreme was to just have a {\it numerical} algorithm,
that for each (numeric!) input $n$, found the output.
In that case the algorithm was rated by its efficiency.
Another compromise was an {\bf asymptotic} formula, valid
(approximately!) for large $n$.
But what's a formula?, it is a kind of algorithm. Of course,
it is more than that, theoretically, but from a practical
point of view it should be judged by the efficiency of the
implied algorithm.
{\bf The Holonomic Ansatz}
Let's look at the explicit formulas that are called
`closed-form', or more precisely {\it hypergeometric} sequences.
A sequence $a(n)$ is called hypergeometric if
the ratio $a(n+1)/a(n)$ is a {\it rational} function of $n$,
i.e. a quotient $P(n)/Q(n)$ where $P(n)$ and $Q(n)$ are polynomials.
For example for the above-mentioned probability of getting exactly
$n$ Heads when tossing a fair coin $2n$ times,
$p(n):=(2n)!/(2^{2n} n!^2)$, we have
$p(n+1)/p(n)=(2n+1)/(2(n+1))$, or, by cross-multiplying
$$
2(n+1)p(n+1)-(2n+1)p(n)=0 \quad.
$$
This is an example of a {\it first}-order {\bf linear recurrence
equation with polynomial coefficients}.
Once you have the trivial value $p(0)=1$ you can use it
to compile a table of $p(n)$ for $n