\documentstyle[a4,12pt]{article}
% \documentclass[a4paper]{article}
% \usepackage{a4}
% \usepackage{latexsym}
%% \usepackage{babel}
\renewcommand{\refname}{Reference}

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newtheorem{Definition} [Theorem] {Definition}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\Remark}{ \noindent{\bf Remark:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\Zz}{{\bf Z}}

\title{Zeilberger-Wilf theory}
\author{A. E. Brouwer}
\date{EIDMA course, 980212 and 980219}
\begin{document}
% \fontsize{12}{14}\selectfont
\maketitle

\medskip

\begin{abstract}
These days it is possible to fully automate certain summations.
\end{abstract}

The problem of discovering whether or not a given hypergeometric
sum is expressible in a simple closed form, and if so, finding that form,
and if not, proving that it is not, has now been completely automated.
No ingenuity required. No mathematician required.
A computer algebra package can do it all.

Recipe for finding $f(n) = \sum_k F(n,k)$:

(i) Go to {\tt \verb#http://www.cis.upenn.edu/~wilf/progs.html#}
and download {\tt EKHAD}. (While you are there you might as well
also take {\tt hyper}, {\tt WZ} and {\tt gosper.m}.)

(ii) Start Maple (some might prefer Mathematica, but that has
a serious flaw: whenever you really need it, it turns out that
your license has expired, or the password of your computer has
changed because you exchanged your ethernet card, and it may
well take a while before it is usable again).

(iii) Read {\tt EKHAD}.

(iv) Define the summand $F(n,k)$.

(v) Call {\tt zeil(F(n,k),k,n,N)}.

(vi) Your problem is solved.

For example, look at the sum $\sum_{k=0}^m (-1)^k {m \choose k}^3$.
For odd $m$ this vanishes since the terms for $k$ and $m-k$ cancel,
so take $m = 2n$.

{\tt
\begin{verbatim}
% maple
    |\^/|     Maple V Release 3 (TU Eindhoven)
._|\|   |/|_. Copyright (c) 1981-1994 by Waterloo Maple Software and the
 \  MAPLE  /  University of Waterloo. All rights reserved. Maple and Maple V
 <____ ____>  are registered trademarks of Waterloo Maple Software.
      |       Type ? for help.
> read EKHAD;

                            Version of Feb. 2, 1998
...
                    This is EKHAD, One of the Maple packages
                             accompanying the book
                                     ``A=B''
                   (published by A.K. Peters, Welesley, 1996)
              by Marko Petkovsek, Herb Wilf, and Doron Zeilberger.

                The most current version is available on WWW at:
                     http://www.math.temple.edu/~zeilberg .
...
> F := (n,k) -> (-1)^k * binomial(2*n,k)^3;

                                       k                 3
                     F := (n,k) -> (-1)  binomial(2 n, k)

> z := zeil(F(n,k),k,n,N);
bytes used=1001168, alloc=786288, time=0.45
bytes used=2001444, alloc=1179432, time=0.95
                                        2
z := - 6 (3 n + 2) (3 n + 1) - 2 (n + 1)  N,

  3                      3         2                   2         2            2
 k  (784 n - 207 k - 48 k  + 2084 n  - 1113 n k + 147 k  - 2214 n  k + 594 n k

              3      4        5         4               3          4
      + 2728 n  + 6 k  + 448 n  + 1760 n  + 116 - 1932 n  k - 624 n  k

             2  2        3  2          3       2  3      4
      + 792 n  k  + 348 n  k  - 132 n k  - 90 n  k  + 9 k  n)

        /               3              3
       /  ((2 n - k + 1)  (2 n + 2 - k) )
      /

>
\end{verbatim}
}

What is it that we found?
The function {\tt zeil} will find recurrences of the form
\begin{equation}
\label{recurr}
\sum_{j=0}^J a_j(n) F(n+j,k) = G(n,k+1) - G(n,k)
\end{equation}
given the function $F(n,k)$.
Once we have such a recurrence, summing over $k$ will yield
$$\sum_{j=0}^J a_j(n) f(n+j) = 0$$
where $f(n) = \sum_k F(n,k)$, a recurrence relation for the
sum that we wanted to find.
In the maple call $N$ is the forward shift operator,
and the first part of the answer says that
$$- 6 (3 n + 2) (3 n + 1) f(n) - 2 (n + 1)^2  f(n+1) = 0$$
that is, $f(n+1) = -3(3n+1)(3n+2)f(n)/(n+1)^2$.
Since $f(0) = 1$ we find that
$$\sum_{k=0}^{2n} (-1)^k {2n \choose k}^3 = (-1)^n { (3n)! \over (n!)^3 } .$$

Interesting. But how can we verify that this really is true?
The second part of the answer is the {\em certificate}, a
rational function $R(n,k)$ that makes it possible to verify
all claims by straightforward checking. It defines the $G$ of
(\ref{recurr}) by $G(n,k) = R(n,k) F(n,k)$. Now dividing both
sides of (\ref{recurr}) by $F(n,k)$ yields a claimed equality
of two rational functions in $n$ and $k$, multiplying by the
denominators yields a claimed equality between polynomials,
and this is true by inspection. Let us verify.

{\tt
\begin{verbatim}
> R := (an,ak) -> subs(n=an,k=ak,z[2]):
> simplify(expand(- 6*(3*n + 2)*(3*n + 1) - 2*(n+1)^2*F(n+1,k)/F(n,k)
> - R(n,k+1)*F(n,k+1)/F(n,k) + R(n,k)));

                                       0

> 
\end{verbatim}
}

(Yes, I am a beginner with Maple; probably there is a better
way to turn the expression {\tt z[2]} into a function in which
we can substitute values for {\tt n} and {\tt k}.)

The final 0 is what we wanted (and we could have done it by hand,
if necessary. This proves our result.

\section{The fundamental theorem}
When precisely does this work?

\begin{Definition}
A function $F(n,k)$ is said to be a {\em proper hypergeometric term}
if it can be written in the form
$$F(n,k) = P(n,k) { \prod_{r=1}^s (a_r n + b_r k + c_r)!
\over \prod_{r=1}^t (u_r n + v_r k + w_r)! } x^k
$$
in which $x$ is an indeterminate, $P$ a polynomial,
the $a_r$, $b_r$, $u_r$, $v_r$ are specific integers
(i.e., do not contain additional parameters) and
$s$, $t$ are finite, nonnegative, specific integers.
(The $c_r$ and $w_r$ are allowed to be arbitrary parameters
that take complex values. Also the coefficients of the polynomial $P$
may contain additional parameters.)
\end{Definition}

\begin{Theorem} {\rm [Mary Celine Fasenmyer]}
If $F(n,k)$ is a proper hypergeometric term, then it satisfies
a recurrence relation
\begin{equation}
\label{celine}
\sum_{i=0}^I \sum_{j=0}^J a_{ij}(n) F(n-j,k-i) = 0
\end{equation}
where the $a_{ij}(n)$ are polynomials in $n$, not all zero,
and the equation holds for all $n$, $k$ for which $F(n,k) \ne 0$
and all occurring $F(n-j,k-i)$ are defined.
Furthermore, there is such a recurrence with $(I,J) = (I_0,J_0)$,
where $J_0 = \sum_r |b_r| + \sum_r |v_r|$ and
$I_0 = 1 + {\rm deg}(P) + J_0(\sum_r |a_r| + \sum_r |u_r| - 1)$.
\end{Theorem}

\Proof
Define (for integral nonnegative $x$)
${\rm rf}(x,y) := \prod_{j=1}^x (y+j)$ and
${\rm ff}(x,y) := \prod_{j=0}^{x-1} (y-j)$.
Let ${\rm ff}(-x,y) := {\rm rf}(x,y)^{-1}$.
(The abbreviations should suggest raising resp. falling factorial.)
Then, if $H(n,k) = (an+bk+c)!$, we have
$${H(n-j,k-i) \over H(n,k)} = {1 \over {\rm ff}(aj+bi,an+bk+c)} . $$
Thus $x^i {F(n-j,k-i) \over F(n,k)}$ is a rational function in $n$, $k$,
say ${\nu_{ij}(n,k) \over \delta_{ij}(n,k)}$, and
$$\delta_{ij}(n,k) = P(n,k) \prod_{a_r j + b_r i \ge 0}
{\rm ff}(a_r j + b_r i, a_r n + b_r k + c_r)
\prod_{u_r j + v_r i < 0} {\rm rf}(-u_r j -v_r i, u_r n + v_r k + w_r).$$
We now try to solve (\ref{celine}) for the coefficients $a_{ij}(n)$.
Place the expressions over a single common denominator, collect the
numerator as a polynomial in $k$, and equate the coefficient of each
power of $k$ to zero. This will work when the number of unknowns
is larger than the number of equations.
Put $x^+ := {\rm max}(x,0)$. Then
$$
{\rm max}\{ aj+bi \mid aj+bi \ge 0,~ 0 \le i \le I,~ 0 \le j \le J \} =
a^+J + b^+I,
$$
$$
{\rm max}\{ -aj-bi \mid aj+bi < 0,~ 0 \le i \le I,~ 0 \le j \le J \} =
(-a)^+J + (-b)^+I.
$$
The least common multiple of all $\delta_{ij}(n,k)$ divides
$$\Delta := P(n,k) \prod_r {\rm ff}(a_r^+J+b_r^+I,a_rn+b_rk+c_r)
\prod_r{\rm rf}((-u_r)^+J+(-v_r)^+I,u_rn+v_rk+w_r) .$$
After multiplying by $x^I \Delta$, we have to find the $a_{ij}(n)$
from he polynomial equation
$$\sum_{i=0}^I \sum_{j=0}^J a_{ij}(n) \nu_{ij}(n,k)
{\Delta \over \delta_{ij}(n,k)} x^{I-i} = 0 .$$
The number of unknowns $a_{ij}$ equals $(I+1)(J+1)$.
The number of different powers of $k$ occurring is at most
$$1 + {\rm deg}(P) + (\sum |a_r| + \sum |u_r|)J +
(\sum |b_r| + \sum |v_r|)I .$$
For sufficiently large $I$, $J$, e.g. for the $I_0$, $J_0$ given
in the theorem, there are more unknowns than equations,
and we find a solution where $a_{ij}$ equals $x^i$ times
a polynomial in $n$.
\qed

\section{Telescoped recurrences}
So, we found, in a constructive way, a recurrence satisfied
by $F(n,k)$. But it is not in a form convenient for summation.

\begin{Theorem} {\rm [Doron Zeilberger]}
If $F(n,k)$ is a proper hypergeometric term, then it satisfies
a nontrivial recurrence relation of the form
\begin{equation}
\label{zeilberger}
\sum_{j=0}^J a_j(n) F(n+j,k) = G(n,k+1) - G(n,k)
\end{equation}
in which $G(n,k)/F(n,k)$ is a rational function of $n$ and $k$.
\end{Theorem}

\Proof
Let $N$, $K$ be the forward shift operators in $n$ and $k$.
Then a recurrence $\sum_{i=0}^I \sum_{j=0}^J a_{ij}(n) F(n+j,k+i) = 0$
can be written as $p(n,N,K) F(n,k) = 0$ for a certain polynomial
$p$ with coefficients in $\Zz[x]$. Take such a $p$ that has minimal
degree in $K$.
Write
$$p(n,N,K) = p(n,N,1) + (1-K)q(n,N,K) .$$
Then
$$p(n,N,1) F(n,k) = (K-1)q(n,N,K)F(n,k) = G(n,k+1) - G(n,k)$$
where $G(n,k) = q(n,N,K) F(n,k)$.
This proves the claim, since shift operators multiply $F(n,k)$
by a rational function.
But could $p(n,N,1)$ be identically zero? Then
$G(n,k)$ does not depend on $k$ and hence is a hypergeometric term
in the single variable $n$ and satisfies some recurrence (of order 1)
$r(n,N) G(n,k) = 0$. Now $r(n,N) q(n,N,K) F(n,k) = 0$, a recurrence
of lower degree in $K$ than the one we started with.
\qed

\section{An example}
As an example of the above theorems, we prove Boersma's identity.
% (Check that this sum really is a special case of the theorems above!)
Define the {\it up-down factorial} ${\rm ud}(x,y)$ by
$${\rm ud}(x,y) := { (x+1)(x+3)...(x+2y-1) \over x(x+2)(x+4)...(x+2y) } .$$

\begin{Theorem}[Boersma, 1961]
Let $a,b,c$ be nonnegative integers such that $a+b+c$ is odd,
and $c \le a+b$. Then
$$\sum_{k=0}^{{\rm min}(b,c)}
{{2b-2k \choose b-k} {2c-2k \choose c-k} {2k \choose k}
\over {2b+2c-2k \choose b+c-k}} .
{(b+c-2k+{1 \over 2}) \over (b+c-k+{1 \over 2})} .
{ 1 \over (a-b-c+2k)(a+b+c+1-2k) }$$
$$= {\rm ud}(a-b-c,c) . {\rm ud}(a+b+1-c,c) .$$
\end{Theorem}
Note that the left hand side is symmetric in $b$ and $c$.
But so is the right hand side: if $c > b$, then the zigzags
from $a-b-c$ to $a-b+c$ and from $a+b+1-c$ to $a+b+1+c$ overlap,
and we see that ${\rm ud}(a-b-c,c) . {\rm ud}(a+b+1-c,c) =
{\rm ud}(a-b-c,b) . {\rm ud}(a+c+1-b,b)$.

{\tt
\begin{verbatim}
> F := (a,b,c,k) -> binomial(2*(b-k),b-k)*binomial(2*(c-k),c-k)*
>   binomial(2*k,k)*(b+c-2*k+1/2) / (binomial(2*(b+c-k),b+c-k) *
>   (b+c-k+1/2)*(a-b-c+2*k)*(a+b+c+1-2*k)):
> T := (c,k) -> F(a,b,c,k):
> z := zeil(T(c,k),k,c,C);
bytes used=245350904, alloc=3276200, time=181.68
z :=

- (c + 2) (c + 1) (a - b + c + 1) (a - b - c - 1) (a + b + c + 2) (a + b - c)

     + (c + 2) (c + 1) (a + b + c + 3) (a + b - c - 1) (a - b + c + 2)

                     2
    (a - b - c - 2) C ,
...
\end{verbatim}
}

Thus, after 3 minutes on a Pentium with Linux (it was 7 minutes
on a Sparcstation with SunOS) we find a recurrence relation
for the sum $S(a,b,c) = \sum F(a,b,c,k)$ of the left hand side.
Here $C$ is the shift operator in $c$. It says
$(c + 2) (c + 1) (a + b + c + 3) (a + b - c - 1) (a - b + c + 2)
(a - b - c - 2) S(a,b,c+2) = (c + 2) (c + 1) (a - b + c + 1) (a - b - c - 1)
(a + b + c + 2) (a + b - c)S(a,b,c).$
This recurrence is valid for all integers $b$ and $c$, and for arbitrary
complex $a$ different from the integers $b+c$, $b+c-2$, ..., $b-c$,
$-b-c-1$, $-b-c+1$, ..., $-b+c-1$ (for $c \le b$).
(We need integers $b$ and $c$ to make sure that only finitely many
summands are nonzero.) For negative $c$ the sum vanishes, for
nonnegative $c$ it is interesting, and the factor $(c + 2) (c + 1)$ in
the relation makes sure we cannot continue the recurrence down past $c = 0$.
Clearly, ${\rm ud}(a-b-c,c) . {\rm ud}(a+b+1-c,c)$ satisfies this
same recurrence (for $c \ge 0$).
It remains to compute $S(a,b,0) = F(a,b,0,0) = 1/(a-b)(a+b+1)$ and
$S(a,b,1) = F(a,b,1,0)+F(a,b,1,1) = (a-b)(a+b+1)/(a+b)(a-b+1)(a+b+2)(a-b-1)$
as desired. \qed

Note that we proved a slightly more general result --- the integrality
of $a$ (and that $a+b+c$ is odd) does not play a role, we only need
$a$ to be a complex number distinct from a handful of given integers.

\section{Another example}
Aart Blokhuis asked for the value of $\sum_{j=0}^k {-a \choose j}
{b \choose k-j} {c+j \choose r}$ for $b = k+a-1$ and $b = k+a-2$,
where $a,b$ are nonnegative integers.
This one is much easier than the previous example. Within two seconds
we find a recurrence relation.

\medskip
But let us first worry a little about the meaning of ${x \choose m}$
for possibly negative $m$. For nonnegative $m$ we have the
definition ${x \choose m} = {x(x-1)...(x-m+1) \over m!} =
{\rm ff}(x,m) / {\rm rf}(0,m)$, valid for all $x$.
Below we shall use the convention ${x \choose m} = 0$ for $m < 0$.
Then ${x+1 \choose m} = {x \choose m} + {x \choose m-1}$ for all integers $m$.

[Note however, that this is not Maple's convention. Indeed, Maple says
for negative $m$ that ${x \choose m} = {\rm ff}(0,-m) / {\rm rf}(x,-m)$
and this is zero, unless $x$ is an integer with $m \le x \le -1$,
in which case ${x \choose m} = {\rm ff}(x,x-m) / {\rm rf}(0,x-m)
= {x \choose x-m}$.
Thus, with this convention we have ${n \choose m} = {n \choose n-m}$
for all integers $m,n$.]

\medskip

\begin{Proposition}
Let $a,b$ be nonnegative integers.

(i) If $b = k+a-1$, we have
$$\sum_{j=0}^k {-a \choose j}{b \choose k-j} {c+j \choose r} =
(-1)^k {b \choose k} {c \choose r-k} .
$$

(ii) If $b = k+a-2$, we have
$$
\sum_{j=0}^k {-a \choose j}{b \choose k-j} {c+j \choose r} =
(-1)^k ({b \choose k}{c \choose r-k} + {b \choose k-1} {c+1 \choose r+1-k})
$$
\end{Proposition}

\Proof
% First of all, if for nonnegative integral $a,b$ we have $b-a < k$,
% then the product ${-a \choose j}{b \choose k-j}$ vanishes for $j < 0$
% and for $j > k$. Thus, we may sum over all integers $j$.

If the sum is $S(k)$, then in the first case we find (regarding
$a,c,r$ as constants) the recurrence $(k-r)(k+a)S(k) = (k+1)(k-r+c+1)S(k+1)$
and $S(0) = {c \choose r}$. The certificate is
$(c + j - r) j (k + a) / (k + 1 - j)$.

In the second case we find the recurrence
$(k - r - 1) (k + a - 1) (k c - k a + a r + 2 k - r + c + 1)S(k) =
(k + 1) (k - r + c + 1) (k c - k a + a r + 2 k - r + a - 1)S(k+1) .$
This means that with $T(k) := S(k)/(kc-ka+ar+2k-r+a-1)$
we have $T(k+1) = {(k-r-1)(k+a-1) \over (k+1)(k-r+c+1)} T(k)$
(essentially the same recurrence as before), so that
$$\sum_{j=0}^k {-a \choose j}{b \choose k-j} {c+j \choose r} =
(-1)^k {b \choose k} {c+1 \choose r+1-k} .
{ k(c+1)+(a-1)(r+1-k) \over (a-1)(c+1) } .$$
\qed

\subsection*{Generalization and a Maple proof}
Inspired by the above we conjecture that
$$
(-1)^k \sum_j {k-b-e-1 \choose j} {b \choose k-j} {c+j \choose r} =
\sum_j {e \choose j} {b \choose k-j} {c+j \choose r-k+j} .
$$

We shall give both a Maple and a traditional proof.
It suffices to prove the identity in case $c = 0$ (see below
for the argument), so we assume this, since it greatly simplifies
the recurrences obtained.

Let $F(r,j)$ and $H(r,j)$ be the summands on the left hand and
right hand side. Then we have for $j \ge 0$
$$
(k-r-e-1)(r+1) F(r+1,j) - (k-r)(k-b-r-e-1) F(r,j) = G(r,j+1)-G(r,j)
$$
and
$$
(k-r-e-1)(r+1) H(r+1,j) - (k-r)(k-b-r-e-1) H(r,j) = J(r,j+1)-J(r,j)
$$
where $G(r,j) = (k-b-j)(j-r) F(r,j)$ and $J(r,j) = (k-b-j)(k-r) H(r,j)$,
as one easily checks by dividing both sides by $F(r,j)$ resp. $H(r,j)$.
(We need not worry about $b = k-j-1$, since both sides are polynomials
in $b$, and if they agree for all nonintegral $b$, they are identical.)
Sum over $j \ge 0$, and note that $G(r,0) = J(r,0) = 0$. We see that both
sums satisfy the same recurrence relation
$$
(k-r-e-1)(r+1) S(r+1) = (k-r)(k-b-r-e-1) S(r) .
$$
Both sums vanish for $r < 0$, and if we check that they agree
for $r = 0$ the recurrence wil show that they always agree.
(Again, we need not worry about $r = k-e-1$.)
But for $r = 0$ we find (this time taking $b$ integral)
$$
(-1)^k \sum_j {k-b-e-1 \choose j} {b \choose k-j} =
(-1)^k {k-e-1 \choose k} = {e \choose k} = 
\sum_j {e \choose j} {b \choose k-j} {j \choose k} .
$$
This proves the claimed identity.

\subsection*{A traditional proof}
Let $\Delta_x$ be the forward difference operator in $x$
(acting on the space of polynomials in $x$), that is,
$\Delta_x f(x) := f(x+1) - f(x)$.
Then $\Delta_x$ decreases the degree of nonzero polynomials
by one (if we agree that the zero polynomial has degree $-1$),
and it follows that $f = g$ when $\Delta_x f = \Delta_x g$
and $f(c) = g(c)$ for some $c$.
This operator is useful when manipulating binomial coefficients,
since $\Delta_x {x \choose m} = {x \choose m-1}$.

\begin{Lemma}
Let $m,n$ be integers, and $m \ge 0$. Then
$$
\sum_i (-1)^i {m \choose i}{x+i \choose n} = (-1)^m {x \choose n-m} .
$$
\end{Lemma}
\Proof
$\Delta_x$ turns this equation into the same equation with $n$
decreased by 1. Thus, it suffices to check this identity for $x = 0$.
Then both sides equal $(-1)^m$ if $n = m$ and 0 otherwise.
\qed

\begin{Proposition}
Let $k,m,n$ be integers. Then
$$
\sum_i (-1)^i {x \choose i} {x+y-i \choose k+m-i} {z+k-i \choose n} =
\sum_i {x \choose k-i} {y \choose m+i} {z+i \choose n-k+i} .
$$
\end{Proposition}
\Proof
$\Delta_y$ and $\Delta_z$ decrease $m$ and $n$, respectively,
so it suffices to prove this for a suitable choice of $y$ and $z$.
Pick $y = 0$ and $z = n-k$. We have to show that
$$
\sum_i (-1)^i {x \choose i} {x-i \choose k+m-i} {n-i \choose n} =
{x \choose k+m} {n-k-m \choose n-k-m} .
$$
But ${x \choose i} {x-i \choose k+m-i} = {x \choose k+m} {k+m \choose i}$,
so it remains to show that if $p \ge 0$ then
$$
\sum_i (-1)^i {p \choose i} {n-i \choose n} = {n-p \choose n-p} .
$$
But this is the case $m = p$, $x = -1$ of the above lemma.
\qed

(Of course the identity we had is obtained by substituting
$b,e,c,0,r,j$ for $x,y,z,m,n,i$ and interchanging $j$ and $k-j$ on the left.)


\begin{thebibliography}{}

\bibitem{PWZ} Marko Petkov\v{s}ek, Herbert S. Wilf \& Doron Zeilberger,
{\it $A = B$}, A.K. Peters, Massachusetts, 1996.

\end{thebibliography}

\end{document}
