\documentclass{amsart}
\usepackage{amsxtra,amssymb,amsmath, amsthm, amsfonts, multicol,graphicx,url, color}
\textheight 22.8cm
\textwidth 15.3cm

\newcommand{\ds}{\displaystyle}
%\renewcommand\refname{\textrm{Further Reading}}
\setlength\parindent{0 pt} \setlength{\parskip}{0.2cm}


\newenvironment{reference}{
\begin{enumerate}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
\setlength{\parindent}{0pt}
}{\end{enumerate}}

\begin{document}
%\maketitle
\rightline{\Huge \bf a WZ-Pair?}
\vskip1cm
\rightline{\it \huge Akalu Tefera}\let\thefootnote\relax\footnotetext{\textsl{Akalu Tefera is Associate Professor of Mathematics\\ at Grand Valley State University. His email address is}\\ \texttt{teferaa@gvsu.edu}}

\vskip1in


\begin{multicols}{2}


One of the most exciting mathematical discoveries in the early 1990's was the Wilf-Zeilberger(WZ) Algorithm that can be used for \textit{proving}, \textit{evaluating} and \textit{searching} identities involving \textit{hypergeometric} terms \emph{automatically} by computer. A discrete function $F(n,k)$ is called \textit{hypergeometric} if both
\[\frac{F(n + 1,k)}{F(n,k)} \mbox{ and } \frac{F(n,k + 1)}{F(n,k)}\] are rational functions of $n$ and $k$. 
The Binomial coefficient ${{n} \choose {k}}=n!/(k!(n-k)!)$, is the simplest (non-trivial) example.

Suppose that 
you are faced with identities of the form $A = B$ where $A$ is a sum of terms  involving hypergeometric terms and $B$ is a conjectured, simpler answer.  
For example, the trivial {\it binomial theorem}
$$
\sum_{k=0}^{n} {{n} \choose {k}} x^k y^{n-k} \, = (x+y)^n, \, \, ,
$$
and the (less trivial) {\it Dixon's identity}
$$
\sum_{k=-n}^{n} (-1)^k {{2n} \choose {n+k}}^3 \, = {{3n}! \over{n!^3}}, \, \,  .
$$
You may ask yourself: ``Is there a computerized method that would \textit{certify} the validity of the identity without human intervention?''
(for {\it all} $n$, not just for many special cases).
Thanks to Herb Wilf and Doron Zeilbrger, the answer is YES!. 
Furthermore, unlike computerized proof techniques in other areas,
the computerized proofs outputted by their method
may be directly verified by {\it mere} humans. This certification is achieved by producing what is called a \emph{WZ-pair}.

\textbf{A WZ-Pair.} A \textit{WZ-pair}, or  \textit{Wilf-Zeilberger pair}, is a pair 
of discrete functions $(F(n,k), G(n,k))$ such that 
$$F(n + 1, k) - F(n,k) = G(n, k + 1) - G(n, k).$$

Suppose that we want to prove an identity of the form
\[
\sum_{k} f(n,k) = r(n) \quad , \quad n \geq n_{0}.
\]
(for some integer $n_0$, usually $0$).
If $r(n) \neq 0$, divide through by $r(n)$ to get
\[
\sum_{k} F(n,k) = 1, \mbox{ where } F(n,k) = f(n,k)/r(n).
\] Let  $S(n) = \sum_{k} F(n,k)$. To show $S(n) = 1$ for all $n \geq n_{0}$, it suffices to show that
 \begin{equation} \label{difference}
 S(n + 1) - S(n) = 0 \mbox{ for all } n \geq n_{0}
 \end{equation}
 and check that $S(n_{0}) = 1$ (usually a trivial check).  A good way to certify (\ref{difference}) would be to display a ``nice'' function $G(n,k)$ such that
\[F(n + 1, k) - F(n,k) = G(n, k + 1) - G(n,k),
\]
for then we simply sum over all integers $k$  to find that (under suitable hypotheses) indeed
\[S(n + 1) - S(n) = 0.\]
(since the sum on the right side is  {\it telescoping}.)

Wilf and Zeilberger proved, in general, that
if the summand is hypergeometric, and $G(n,k)$ exists (and surprisingly it does in 99.99 percents of the cases where $r(n)$ is ``nice'',
and whenever it does, it can be easily found by their algorithm, that is based on the so-called Gosper algorithm),
$G$ has the form: \[G(n,k) = C(n,k)\, F(n,k).\] Here $C$ is rational in both $n$ and $k$, and is called the \textit{WZ proof certificate}.

If $r(n)$ is not ``nice'' then the so-called Zeilberger algorithm guarantees that it is {\it holonomic} (a solution of a linear
recurrence equation with polynomial coefficients.

The WZ algorithm is implemented in Zeilberger's Maple package
\texttt{EKHAD} available from \url{www.math.rutgers.edu/~zeilberg/}
and the  built-in \texttt{SumTools} package in Maple. A Mathematica package written by Peter Paule and
Markus Schorn is also available.

\textbf{Example.} Suppose we want to prove:
 \[\sum_{k} (-1)^k\binom{n}{k}\binom{2 k}{k} 4^{n - k} = \binom{2 n}{n}.
\]

Applying the WZ algorithm to the summand  $(-1)^k\binom{n}{k}\binom{2 k}{k} 4^{n - k}$, yields a WZ-Pair $(F, G)$, where
\[F(n,k) = \frac{(-1)^k\binom{n}{k}\binom{2 k}{k} 4^{n - k}}{\binom{2 n}{n}},\]
 \[G(n,k) = C(n,k) F(n,k) \mbox{ and}\]
\[C(n,k) = - \frac{2 k^{2}}{(n+1 - k)(2 n+1)}.\]


\textbf{Doubling the fun!} Besides getting a very short proof for any given summation identity, one can discover a new identity from a WZ-pair. Here is how. Suppose the identity
\[\sum_{k} F(n,k) = r(n), (n \geq n_{0})\]
yields a WZ-pair $(F, G)$. If the WZ-pair satisfies (i) for each $k$, $\ds  f_{k} := \lim_{n \to \infty} F(n,k)  < \infty$   and
(ii) $\ds \lim_{L \to \infty} \sum_{n \geq n_{0}} G(n, L) = 0$, then we get a new identity
\[
\sum_{n \geq n_{0}} G(n,k) = \sum_{j \leq k - 1} (f_{j} - F(n_{0},j)).
\]

\textbf{Example.} The identity
\[\sum_{k} k \binom{n}{k} = n 2^{n - 1}, \quad n \geq 1\]
  has a WZ-pair $(F, G)$, where
\[F = \frac{k}{2^{n - 1} n} \binom{n}{k} \mbox{ and } G = -\frac{1}{2^{n}}\binom{n - 1}{k - 2}.\] Furthermore, the WZ-pair satisfies the above conditions, and hence we have a new identity
\[
\sum_{n = 1}^{\infty} \frac{1}{2^{n}}\binom{n - 1}{k - 2} = \left \{ \begin{array}{r @ {\quad} l} 1 & \mbox{if } k \geq 2\\ 0 & \mbox{otherwise}  \end{array} \right..
\]


\textbf{Finding closed forms for sums.} Does the WZ method apply to find directly the $B$ part of  $A  = B$? The answer is yes whenever the summands in $A$ are \textit{proper-hypergeometric}. A discrete function $F(n,k)$ is \textit{proper-hypergeometric} if it can be written in the form:
\[
P(n,k)\frac{\prod_{i = 1 }^{I} (a_{i}n + b_{i}k + c_{i})!}{\prod_{j  = 1}^{J} (u_{j}n + v_{j}k + w_{j})!} x^{n}y^{k},
\]
where
\begin{itemize}
\item $P(n,k)$ is a polynomial in $n$ and $k$,
 \item $I$ and $J$ are fixed integers,
  \item  $a_{i}, b_{i}, u_{j}, v_{j}$ are integers, and
 \item  $c_{i}, w_{j}, x, y$ may depend on parameters.
\end{itemize}
Finding closed forms for sums relies on  the fundamental theorem of WZ theory which  states that if $F(n,k)$  is a proper-hypergeometric term, then there exists a (proper)  hypergeometric term $G(n,k)$ such that
\begin{equation}
\label{FundThm}
\sum_{j = 0}^{J} a_{j}(n)F(n + j, k) = G(n, k + 1) - G(n,k),
\end{equation}
where $a_{j}(n)$ are polynomials in $n$. Suppose we want to find a closed form expression for
 \[S(n) = \sum_{k} F(n,k)
\]where $F$ is a proper-hypergeometric. Then by the fundamental theorem we get a recurrence equation of the form (\ref{FundThm}) for $F(n,k)$. Summing both sides of $(\ref{FundThm})$ with respect to $k$ yields
\[
\sum_{j = 0}^{J} a_{j}(n)S(n) = 0 \quad .
\]
(assuming, as is usually the case that $G(n, \pm \infty)=0$).
If the order of the recurrence, $J$, happens to be $1$, then we can easily solve this recurrence
and get the closed-form solution. If $J>1$, then
Petkov\v{s}ek algorithm's can be used to find a closed-form solution, if one exists, or else rule out this possibility.
Either way, describing a sequence $\{S(n)\}$ in terms of the linear recurrence equation with polynomial coefficients
that it satisfies, together with the initial conditions ($S(0),S(1), \dots , S(J-1)$) is an effective and
{\it canonical way} to describe it, and is almost as good as ``closed-form''. The recurrence can also be used
to compute, in linear time, and constant memory, as many terms as desired.


\textbf{Proving identities of the form $A = B$ when $B$ has no simple form.} Suppose we want to prove identities of the form \[\sum_{k} F(n,k) = \sum_{k} H(n,k),\, (n \geq n_{0}).\]

Let $L(n)$ and $R(n)$  be the left and right sides of the equation.
Find recurrences for each side, and see whether they coincide, and check the initial conditions.

\textbf{Further Reading}
\begin{itemize}
\item[[1\!\!]] M. Petkov\v{s}ek, H. S. Wilf, and D. Zeilberger,
\textit{A = B}, A. K. Peters, Wellesley, Massachusetts, 1996.
\item[[2\!\!]]  H. Wilf  and D. Zeilberger, \textit{Rational function certify combinatorial identities}, J. Amer. Math. Soc. \textbf{3 }(1990),  147-158.
\end{itemize}
\end{multicols}



\end{document} 

