%begin macros
\parskip=8pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
%end macros
\rm
{\bf IDENTITIES IN SEARCH OF IDENTITY}
\footnote{$^1$}{
Written version of an invited talk presented at the \it
Series
Formelles et Combinatoire Algebrique\rm
 conference, May 2-4, 1991,
Bordeaux, France. Delivered on May 4, 9:00 AM (local time), about
seven hours after the end of the {\it soir\'ee officiel} consisting
of a royal dinner and extensive wine tasting, in which the average
bottle of wine was consumed by half a participant.
}

{\it Doron Zeilberger}
\footnote{$^2$}{
Department of Mathematics, Temple University,
Philadelphia, PA19122. E-mail address:
zeilberg@euclid.math.temple.edu.
Supported in part by NSF grant DMS8901690.
}

{\bf Appeared in:} J. Theoretical Computer Science, {\bf 117}(1993), 23-38.

{\bf Abstract:} The time is ripe to start a science of identities
for their own sake, without paying lip-service to high-brow
mathematics. Although putting combinatorial, (abstract-)
algebraic or analytic
flesh and blood on identities did lead and will lead to
considerable insight as well as new identities, there is
also much to be gained in forgetting advanced mathematics,
and starting a new sub-discipline of high-school mathematics called
"the theory of identities".

{\bf Preamble:} I would like to add to Xavier Viennot's
charming after-dinner speech, in which he listed a large set
of properties that conferences may have, and which were
all enjoyed by the present one, in addition to "something special
that comes from the heart", the following. There are
many conferences in which a Bourbaki is an invited speaker,
and many conferences in which a software developer is an invited
speaker, but this one is the first one, that I know of, that
has both (Pierre Cartier and Gaston Gonnet, respectively.) So we are
nearing the blissful days of the mathematical messiah in which
{\it Concrete shall dwell with Abstract}.

Mathematics is a {\it language}. The most basic elements of a language
are its {\it letters\rm
, or \it
characters}. One of the most important
"letters" of mathematics is

$$
   \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, = \, \, \, \, \,. 
$$

{\bf Definition}: A mathematical sentence that has "=" in its middle
is called an {\it identity}.

The format of an identity is thus

          SOMETHING = SOMETHING ELSE.

{\bf Trivial Example:} $Re(s)=1/2$, for every complex zero $s$ of
$\zeta (s)$.

{\bf Easy Example:} ANALYTIC INDEX = TOPOLOGICAL INDEX.

{\bf Deep Example:} 1+1=2.

Related to the subject of identities, or {\it equalities} is the
more difficult subject of {\it inequalities}. Very
often important inequalities are immediate consequences of related
equalities, but of course, finding the right equality is not always
easy. For example the celebrated identity

$$
  {{a+b}\over {2}} \geq \sqrt ab  \, \,follows \,from \,the \,(trivial) \,equality \, \, {{a+b}\over {2}} - \sqrt ab = {{ ( \sqrt a - \sqrt b )^2 }\over{2}} \, \, \,. 
$$

A similar phenomenon occurs with

$$
  3 + 4 cos \theta + cos ( 2 \theta ) \geq 0 \, \,, 
$$

of prime-number-fame, that follows immediately from the (trivial)
equality

$$
  3 + 4 cos \theta + cos ( 2 \theta ) = 2( 1+ cos \theta )^{2 \, \,}. 
$$

A far less trivial example is

$$
  {}_3 F_2  (   {   {-n, n+ \alpha + 2 , ( \alpha +1) /2} \atop   { ( \alpha +3 )/2 , \alpha +1} }  \,; \, t  \, \, )  \, \,\geq 0  \, \,, 
$$

which is the Askey-Gasper inequality of Bieberbach ([deB]) fame.
It is an immediate consequence of the stronger Askey-Gasper
{\it equality}:

$$
  {}_3 F_2  (   {   {-n, n+ \alpha + 2 , ( \alpha +1) /2} \atop   { ( \alpha +3 )/2 , \alpha +1} } ; t  )  \,= \, \sum_{j} EXPLICIT(n,j)^{2 \, \,,} 
$$

where "$EXPLICIT(n,j)$" is a certain explicit {\it real} quantity,
see the paper by Ekhad[E5] in this issue.

An even deeper inequality is the following, for which I don't
know any corresponding equality, not even conjectured, and I
sure wish I did.

$$
  \Delta (X,Y)  \,\geq \, 0 \, \,, 
$$

where

$$
  \Delta (x,y) := \int_{- \infty}^{\infty} \int_{- \infty}^{\infty} \Phi (t) \Phi (s) e^{i(t+s)x} e^{(t-s)y} (t-s)^2 dt ds \, \,, 
$$

$$
  \Phi (t) := \sum_{n=1}^{\infty} (2 pi^2 n^4 e^{9t} - 3 \pi n^2 e^{5t} ) e^{- \pi n^2 e^{4t} } \, \, \,. 
$$

Jensen (see [Va]) 
showed that this inequality is equivalent to the Riemann 
Hypothesis.

A random sampler of other famous identities is

$$
 \sum_{ \lambda |- n } f_{\lambda}^2  \,= \,n! \, \,, 
\eqno(Young-Frobenius)
$$          

$$
 \sum_{\lambda}  s_{\lambda} ( {\bf x} ) s_{\lambda} ( {\bf y} ) =  \prod_{i=1}^{\infty}  \, \,\prod_{j=1}^{\infty} {{1}\over{1- x_i y_j }} \, \,, 
\eqno(Cauchy)
$$      

$$
 \sum_{\lambda} s_{\lambda} ( {\bf x} ) =  \prod_{i=1}^{\infty} {{1}\over{1- x_i }} \, \, \prod_{i=1}^{\infty}  \, \,\prod_{j=i+1}^{\infty} {{1}\over{1- x_i x_j }} \, \,, 
\eqno(Littlewood)
$$     

$$
 \prod_{ \alpha  \epsilon  R^+ } (1- x^{\alpha} )  \,= \, \sum_{ w  \epsilon  W } x^{ w ( \delta ) - \delta } \, \,, 
\eqno(Weyl)
$$        

$$
 \sum_{w  \epsilon  W} w ( \prod_{ \alpha  \epsilon  R^+ }  {{1-t x^{\alpha} } \over {1- x^{\alpha} }} ) \,= \, \prod_{i=1}^{l} 
{{(1- t^{d_i} )} \over {1-t}} \, \, \,, 
\eqno(Macdonald)
$$        

$$
 C.T. \prod_{ \alpha  \epsilon  R^+ } (1- x^{\alpha} ) ... (1- q^{a-1} x^{\alpha} ) (1- q x^{- \alpha} ) ... (1- q^a x^{- \alpha} )  \,= \, \prod_{i=1}^{l}   [  { { d_i a } \atop a }  ] \, \,, 
\eqno(Macdonald')
$$     

$$
 \sum_{n=0}^{\infty}   {{q^{n^2} }\over{(1-q)(1- q^2 ) ... ( 1- q^n ) }} \, \, \,= \, \, \, \prod_{n=0}^{\infty} 
{ {1} \over {(1- q^{5n+1} )(1- q^{5n+4} )} }\, \, \,, 
\eqno(R-R)
$$      

$$
 \sum_{n=1}^{\infty} {{1}\over{n^3}} = {{5}\over {2}} \sum_{n=1}^{\infty} {{(-1)^{n-1}} \over { n^3  (  { 2n \atop n }  ) }} \, \, \,. 
\eqno(Apery)
$$        

{\bf SYNTAX vs. SEMANTICS} 

There are (at least) two approaches to mathematics (or life
for that matter.) The {\it syntactical} approach, that looks at
the {\it form}
 or {\it format} of things, and the 
{\it semantical} approach, that looks for 
{\it substance}, {\it meaning} etc. Logic and much of computer science are
syntactical, but of course once you have a syntactical
{\it theory}, 
it is a theory, hence a {\it
meaningful} theory, and
hence has meaning. In a sense, all of mathematics is syntactical,
because it looks for the form of things.  Marshal Mcluhan said
that yesterday's form is tomorrow's content, and so on, so
one has an infinite onion, and everything is both semantical
and syntactical. In particular:

NOBODY HAS A MONOPOLY ON MEANING AND INSIGHT.

One of the greatest triumphs of the syntactical approach is
Schutzenberger's approach of coding combinatorial objects
as words in formal languages. This was used very successfully
by the {\it ecole bordelaise} (e.g. [D-V].)
Another major success, partially inspired by the former, is the
beautiful combinatorial approach of Foata and the \it
\'ecole lotharingien\rm to special function identities (e.g. [Fo]). 
In it, one abandons
the "analytical" meaning of special functions qua functions, and
looks at the identities {\it syntactically} as a formal relations
amongst {\it formal power series}, making issues of convergence
superfluous, and, in fact, {\it meaningless}, since what used
to be (real, complex, or whatever) {\it variables\rm
, \it
denoted}
by {\it letters}, become the letters themselves, i.e. turn into
(usually commuting) {\it indeterminates}. Then one introduces
a combinatorial structure, for which the given relation is the "shadow",
i.e. the {\it weight enumerator}, according to appropriate
{\it statistics}. I should also
mention the extremely fruitful {\it species},
pursued vigorously by the ecole Qu\'ebecoise  (e.g [B-L-L])
that once again, can be viewed both as a syntactical theory and as
a semantical theory.

Semantical creatures always look for meaning and insight. Many
times they find it, and it's great. Other times they find it,
and {\it who cares?}, 50 pages of semantical conceptual abstract
nonsense to "understand" some identity. Yet other times, the
insight is completely in the beholder's eyes, like a Rorschach test.

Also what constitutes "insight" is a matter of personal taste.
To fancy algebraists,

INSIGHT=REPRESENTATION THEORY PROOF.

To combinatorialists, on the other hand,

INSIGHT= COMBINATORIAL (PREFERABLY BIJECTIVE) PROOF,

while some folks don't care at all about insight. They only
care whether a result is true or false. Shalosh B. Ekhad
belongs to the latter category.

Take for example the good old Young-Frobenius identity

$$
 n! \,= \, \sum_{ \lambda |- n } f_{\lambda} f_{\lambda \, \, \,}. 
\eqno(Y-F)
$$          

The representation theory proof says that both sides count
the dimension of the regular representation of $S_n$.
The right side, because the multiplicity
of the  irreducible representation $\lambda$ in the regular
representation equals its dimension $f_{\lambda}$. See
Bruce Sagan's [Sa] recent beautifully written book.
\footnote{$^3$}{
I only take issue with p. 96, line 3, word 9: "(complicated)"
should be replaced by "deep and intricate, yet gorgeous".
}

The combinatorial proof of the Young-Frobenius identity is
through the Robinson-Schensted bijection. The left hand
side counts the {\it cardinality} of $S_n$, while
the right hand side counts the cardinality of pairs of tableaux
of the same shape, having $n$ cells. That they are equinumerous
follows from the fact that they are in {\it bijection}.

However, there is a short proof of this identity
(due, I think, to Robinson, and that was shown to me
a long time ago by Herb Wilf), that only uses high-school
algebra. It goes as follows. First one proves

$$
 n f_{\lambda} = \sum_{ \lambda^+ \rightarrow \lambda } f_{\lambda^+} \, \,. 
\eqno(*)
$$         

Recall that $f_{\lambda}$ is defined as the number of 
standard tableaux of shape $lambda$, or equivalently, the
number of {\it paths} in Young's lattice 
$\lambda = \lambda^{(n)} \rightarrow \lambda^{(n-1)} \rightarrow \lambda^{(n-2)}$
$\rightarrow ... \rightarrow empty$, where $\lambda \rightarrow \mu$ means that $\mu$ is
a subshape of $lambda$, and they differ by one cell. They
satisfy the obvious recurrence

$$
 f_{\lambda}  \,= \, \sum_{ \lambda^- \leftarrow \lambda } 
f_{\lambda^-}  \, \,. 
\eqno(**)
$$         

Now one proves (*) by induction, using (**).

$$
  n f_{\lambda}  \,=^{(**) \,}  f_{\lambda} +  \sum_{ \lambda^- \leftarrow \lambda }  (n-1) f_{\lambda^-}  \,=^{(*)_{n-1} }  \, f_{\lambda} + \sum_{ \lambda^- \leftarrow \lambda }   \, \,\sum_{ \lambda^{- +}  \rightarrow \lambda^-  } f_{\lambda^{- +}  } \, \, \,. 
$$

Now the summation set {$lambda^{- +} $} is the set of all shapes
obtained by deleting a cell and then adding a cell. This set it
"almost" the set {$lambda^{+ -}$} obtained by adding a cell and
then deleting one. Indeed if the deleted cell and the added cell
are distint, then there is a 1-1 correspondence between
the action of delete-then-add and that of add-then-delete. The
only possible discrepancy is when the added and deleted cells are
the same. The number of ways of deleting a cell and then adding it
back equals the number of distinct parts
of the shape, while the number of ways
of adding-then-deleting is the number of distinct parts
plus one, since one
can add a new row of one cell at the very bottom (and then 
delete it). So, as multisets, we have

$$
  \{\lambda^{+ -} \} = \lambda \cup \{ \lambda^{- +} \} \,. 
$$

Putting this above, and using (**) once again, we get that

$$
  n f_{\lambda} =  \sum_{ \lambda^+ \rightarrow \lambda }   \, \,\sum_{ \lambda^{+ -} \leftarrow \lambda^+  } f_{\lambda^{+ -} }  \,= \, \sum_{ \lambda^+ \rightarrow \lambda } f_{\lambda^+} \, \,.  \, \,QED 
$$

The readers are invited to show how (*) implies (Y-F).
A careful scrutiny of the proof shows that it is in fact the
"algebraization" of the Robinson-Schensted proof, and conversely,
the Robinson-Schensted algorithm is the "bijectification" of the
above proof.

{\bf A NEW SCIENCE IS BORN}

I propose to start a new SCIENCE, to be called
IDENTITY SCIENCE (IS for short). In it identities will be
studied for their own sake, and one will try to use
the minimum amount of concepts, at least of concepts from
other parts of mathematics. Group theoretical, combinatorial
and other conceptual and insightful proofs will be banned,
{\it except} when there is hope of stripping the foreign
concepts away. This fanaticism will serve a very important
purpose. I believe, with Hemingway, that {\it less is more},
and with modern painters and composers that \it
extreme
ugliness is beautiful\rm
on "no conceptual proofs please" is based on the following
hope:

COMPLETE LACK OF INSIGHT WILL LEAD TO NEW KINDS OF INSIGHTS.

I will now give a few examples of families of identities, drawn
from my own personal experience, and will try and rate them
according to whether they are
{\it utterly trivial\rm
, \it
trivial}, \it trivial
but expensive\rm
, {\it trivial in principle}, and 
{\it not yet trivial}. Since the word "trivial" has an offensive
ring to it,
I will replace it by {\it shaloshable}, in honor of my
faithful servant Shalosh B. Ekhad.

At the bottom of the ladder are {\it rational function identities}
with a fixed
number of terms and variables. For example

$$
  {{1}\over {x}}  \,+ \, {{1}\over {y}}  \,+ \, {{1}\over {z}} = {{xy+xz+yz}\over {xyz}} \, \,. 
$$

These are, of course, utterly shaloshable. {\it Not yet shaloshable}
are rational function identities 
with an {\it arbitrary number of variables}
and terms, for example, the so-called Good identity, that was used
by Good[Go] to give a 1-line proof of Dyson's conjecture:

$$
  \sum_{i=1}^{n} {{1} \over {\prod_{j \neq  i} (1- x_i / x_j )}}  \,= \,1 \, \, \,, 
$$

which is an easy, albeit human, exercise in using Lagrange
interpolation: put $p(x) = 1$, and then $x=0$ in

$$
 p(x) = \sum_{i=1}^{n} p( x_i ) {{\prod_{j \neq  i} (x - x_j ) } \over {\prod_{j \neq  i} (x_i - x_j ) }} \, \,. 
\eqno(Lagrange)
$$      

It would be nice to define precisely a wide
class of "Good" identities, perhaps those involving
$\sum$ and $\prod$ a finite number of times, with the ranges of
summation and product having a certain form, and make them
shaloshable, perhaps by mechanizing Lagrange interpolation.

The next level of identities are 
{\it single sum binomial coefficient identities}. These can
always be written in the form

$$
   {\sum \prod  \,= \, \prod} \, \, \,, 
$$

or more verbosely,

$$
  \sum_{k= - \infty }^{\infty} \prod_{k'=1}^{k} R(n,k')= Constant  \,\cdot  \,\prod_{n'=1}^{n} S(n') \, \, \,, 
$$

where both $R(n,k')$ and $S(n')$ are rational functions of their
arguments.

For example, the good old binomial theorem can be written as

$$
  \sum_{k= - \infty }^{\infty}  \, \,\prod_{k'=1}^{k} {{n-k'+1}\over {k'}}  \,= \, \prod_{n'=1}^{n} 2 \, \, \,. 
$$

The same "atomic" notation can be used for \it
multi-sum binomial
coefficients identities. \rm 
For example, the trinomial theorem
can be written as

$$
 \sum_{k_1 = - \infty }^{\infty}   \,\sum_{k_2 = - \infty }^{\infty}   \,\prod_{k'_1 = 1 }^{ k_1} {{n- k'_1 +1}\over{k'_1}}  \,\prod_{k'_2 = 1 }^{ k_2} {{n- k_1 - k'_2  +1}\over{k'_2}} \,= \, \prod_{n'=1}^{n} 3 \, \, \,. 
\eqno(trinomial)
$$     

We now know
\footnote{$^4$}{
[Z1][Z2][Z3][Z5][WZ1][WZ2] (see also [A-Z]), 
but this goes back to my error-ridden Sister
Celine paper [Z0], in which I tried to show
that "all binomial coefficients
identities are trivial" by basing this on a formalization of Sister
Celine's technique, that was done sloppily and inaccurately. Recently
Peter Paule pointed my attention to a paper by Verbaeten of 1974,
[Ve], that formalizes Sister Celine's technique {\it correctly}. However
both Sister Celine and Verbaeten were only interested in {\it finding}
recurrence relations for polynomials. The significance for proving
identities was first realized in [Z0]. So were it possible to
rewrite history, like it used to be in some countries, I would
have rewritten [Z0] with full reference to [Ve].
}
that

ALL BINOMIAL COEFFICIENT ($\equiv$ HYPERGEOMETRIC) IDENTITIES ARE SHALOSHABLE.

The format of the most common binomial coefficient identity is

$$
  \sum_{k} NICE(n,k) \,= \overline{\,NICE} (n) \, \,, 
$$

where a function $F(n,k)$ is "nice" if it's closed form ($F(n+1,k)/F(n,k)$
and $F(n,k+1)/F(n,k)$ are rational functions,) and, to avoid pathologies
like $1/(n+ k^2 )$, we also require that it's holonomic (see[Z1]).
For example

$$
   \, \,\sum_{k}  (  { n \atop k}  )  \,= \, 2^{n \, \, \,, \, \,} \sum_{k}  (  { n \atop k}  )^2  \,= \,   (  { 2n \atop n}  )  \, \,,  \, \, \,\sum_{k} (-1)^k  (  { 2n \atop n+k}  )^3  \,= \,  {{(3n)!}\over{n!^3}} \, \, \,. 
$$

Let's describe the {\it WZ methodology}[WZ2] of proving such
identities. First make the right hand side as nice as can be:

$$
  \sum_{k} {{NICE(n,k)}\over {\overline{NICE}(n)} } \,= \,1 \,. 
$$

Of course {\it thou shall not divide by zero}, so if $\overline{NICE}$
is identically zero, then, just let it be.
Now let's call the summand above $F(n,k)$, and we have to prove that
its definite sum from $k=- \infty$ to $k= \infty$ is identically $1$
(or zero.) It turns out ([WZ1],[WZ2]) that there always
\footnote{$^5$}{
Well, almost always, and something more general, that still enables
us to prove the identity, is always true, see [WZ2][Z2].
}
exists a {\it WZ mate}, $G(n,k)$, such that the following is
true

$$
 F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k) \, \, \,. 
\eqno(WZ)
$$          

Not only that,

$$
  G(n,k)=RATIONAL(n,k) \cdot F(n,k) \, \,. 
$$

{\bf META-THEOREM}:  FOR ANY GIVEN BINOMIAL COEFFICIENTS IDENTITY, 
VERIFYING (WZ) IS A PURELY ROUTINE MATTER

{\bf Proof:} Dividing (WZ) by $F(n,k)$, we have to verify

$$
  {{F(n+1,k)}\over {F(n,k)}} -1  \,= \, {{G(n,k+1)}\over {F(n,k+1)}} \times {{F(n,k+1)}\over {F(n,k)}} - {{G(n,k)}\over {F(n,k)}} \, \, \,. 
$$

Since $F$ is closed-form, and from the fact that $G/F$ is a rational
function, it follows that 
all the above ratios are rational functions, and hence
the identity is routinely verifiable.

Let's give a WZ proof of $(1+1)^2 = 2^n$.

{\bf Verbose Proof:} We have to prove

$$
  \sum_{k} {{  (  {n \atop k}  ) }\over{ 2^n}}  \,= \,1. 
$$

We cleverly construct 

$$
  G(n,k):= {{-1} \over {2^{n+1}}}  (  {n \atop k-1}  ) \,( \,= {{\,-k}\over{2 (n-k+1)}} F(n,k) \,) \,, 
$$

with the motive that

$$
 F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k) \, \, \,, \,(check!) \,, 
\eqno(WZ)
$$          

Summing (WZ) with respect to $k$ gives

$$
   \sum_{k} F(n+1,k)- \sum_{k} F(n,k)= \sum_{k} ( G(n,k+1)-G(n,k))  \,= \,0,(by \,telescoping). 
$$

$$
  So \, \,L(n):= \sum_{k} F(n,k) \,, \,satisfies \, \, L(n+1) \,- \,L(n)=0 \,for \,every \,n \geq 0 \,. 
$$

Since $L(0)=1$ (check!), it follows that $L(n) \equiv 1$. QED

All WZ proofs have the same monotone style, after all they were
generated by a (deterministic) program. After a few identities
they become repetitive. The only thing that changes is the
input $F(n,k)$ (given by the "theorem" part) and the
corresponding output, $G(n,k)$, that is always of the form
$R(n,k) F(n,k)$, for some {\it rational function} $R(n,k)$.
Assuming that the reader is familiar with the WZ methodology,
that can be explained once and for all, all that the prover
has to supply is the rational function $R(n,k)$. Thus 

{\bf Terse Proof:}

$$
  R(n,k) \,= \, {{-k}\over {2(n-k+1)}} \, \, \,QED \, \,. 
$$

However, MAPLE is readily available (for $<$  1000 US dollars), and my
program is available for free. Since $R(n,k)$ can be easily
reproduced by any computer, it is even unnecessary to present
the rational function. Thus,

{\bf An Even Terser Proof:}      QED .
\footnote{$^6$}{
This is reminiscent of an old Jewish joke. The proud father
of a newborn son wants to inform, via telegram, his father
(the baby's grandfather), of the event, so that he can come
to the {\it brit} (ritual circumcision.) The first version
he had was: "Dear Papa, Please come to the brit of your newborn
grandson". Since every word costs money, he is trying to see
if he can make it shorter. First he gets rid of the words
"Dear", then "please", then "Papa", then "newborn" (it must
be newborn) then  "grandson" (whoever heard of a brit for a daughter),
and so on, until he gets the empty telegram. He then feels
silly about sending an empty telegram, and forgets about the
whole thing. Of course, the mistake was at the end. Had
the grandfather received an empty telegram, it would have signaled to
him that something important happened to his son, that necessitated
visiting him. Similarly, in the "even terser proof",one is
not allowed to drop the "QED", or if one has {\it imperial}
tastes (see Paulos's masterpiece [Pa]), 
the QED. The "QED" is the writer's word of honor
that he actually ran the program, and it did produce a certain
$R(n,k)$. 
}

Since the WZ method is not yet as well known as it should be,
at present Shalosh B. Ekhad uses the "terse" style, but not yet
the "even terser" style. For an impressive example of what
Shalosh can do, see its paper [E5] in this issue. See also
[E1-4],[E-Z].

It is not true {\it in general}, that

$$
  L(n):= \sum_{k} NICE(n,k) \, \, \,, 
$$

is itself always "nice", but something {\it weaker} is always true.
For $L(n)$ to be nice, it has to satisfy

$$
  {{L(n+1)}\over {L(n)}}  \,= {{\,POL(n)}\over {POL'(n)}} \, \,, \, \,i.e. \,, 
$$

$$
  POL'(n)L(n+1)-POL(n)L(n) \,= \,0, 
$$

which is a {\it first order homogeneous} linear recurrence
equation with polynomial coefficients. In general $L(n)$ is
guaranteed ([Z0],[Z1]) to be a solution of some
linear recurrence equation with polynomial coefficients, but
not necessarily of first order. Such $L(n)$ are called
{\it P-recursive} or {\it holonomic}. So $L(n)$ satisfies
an equation of the form

$$
  POL(n)L(n)+POL'(n)L(n+1)+POL''(n)L(n+2)+ ... POL^{(s)} (n) L(n+s)  \,= \,0, 
$$

{\bf Example:}

$$
  L(n):= \sum_{k}  (  { n-k \atop k }  ) \, \,satisfies \, \, L(n)-L(n-1)-L(n-2) \,= \,0. 
$$

It follows that all the identities of the form

$$
  \sum \prod RATIONAL  \,= \, \sum \prod RATIONAL' \, \,or \, \,equivalently \sum_{k} NICE(n,k)  \,= \, \sum_{k} NICE'(n,k) \, \,, 
$$

are shaloshable. Just find recurrences for either sides and check
whether they are the same, or at least "equivalent", and that
the appropriate boundary conditions match.

All the "hairy" parts in Ap\'ery's [Ap] proof that
$\zeta (3)$ is irrational ([vdP]) are shaloshable (see [Z4]). Indeed,
Shalosh can prove in a few seconds that

$$
  b(n):= \sum_{k}  (  { n \atop k }  )^2  (  { n+k \atop k }  )^{2 \, \,,} 
$$

and

$$
  a(n):= \sum_{k}  (  { n \atop k }  )^2  (  { n+k \atop k }  )^2  [ \sum_{m=1}^{n} {{1}\over{m^3}} + \sum_{m=1}^{k} {{(-1)^{m+1}} \over {2 m^3  \, \,  (  { n \atop m }  )  (  { n+m \atop m }  )}}  ] \, \,, 
$$

are solutions of

$$
  n^3 x_n - (34 n^3 - 51 n^2 + 27 n -5) x_{n-1} + (n-1)^3 x_{n-2 \, \,= \, \,0}. 
$$

Proof:QED.

The WZ method, and the more general method of [Z2] found
many {\it new} identities, in addition to proving 
many known ones (and being able to prove {\it all} 
terminating single-sum hypergeometric
identities.) However, being "new" doesn't mean "interesting".
As was pointed out by Blackwell, it is possible to discover
a {\it new} identity by taking any two 10-digit numbers and
then multiplying them together, and the resulting identity is most
likely new. What we want is {\it new and interesting}.
Even more exciting would be a use of the WZ {\it method}
to prove an identity needed by someone {\it desperately}
in order to prove an open problem. Such a dramatic use
of the WZ method was recently given by George Andrews [An],
who, in the course of his proof of the Mills-Robbins-Rumsey
conjecture about the number of totally symmetric, self complementary
plane partitions, needed to evaluate

$$
  {}_4 F_3   (  { {-i \,, \, 8/3 \,, \,j+3 \,, \,5/2}  \atop                {5/3 \,, \,-2j \,, \,2j+6}              } \,; \, -8    ) \, \, \,, 
$$

which he was unable to do by any of the previously known methods.
The WZ method solved it in a few seconds. 

Everything discussed  so far applies just as well to q-analogues,
except that the {\it WZ} miracle doesn't happen so often, and
one does have to resort to q-creative telescoping [WZ3].

{\bf Definition:} $a(n)$ is q-nice if

$$
  {{a(n+1)}\over {a(n)}}  \,= \,RATIONAL(q, q^n ) \, \, \,. 
$$

The prototype of a q-nice function is the q-analog of $n!$:
$(q)_n  \,:= \, (1-q) (1- q^2 ) ... ( 1- q^n )$.

By the same token, a function $F(n,k)$ of two discrete variables
is $q-nice$ if

$$
  {{F(n+1,k)}\over {F(n,k)}}  \,= \, R_1 ( q^n , q^k , q ) \, \, , {{F(n,k+1)}\over {F(n,k)}}  \,= \, R_2 ( q^n , q^k , q ) \, \, , 
$$
where $R_1 $ and $R_2$ are rational functions of all their
arguments. The obvious extension holds for functions
$F( k_1 , ... , k_r )$ of several discrete variables.
Particularly nice closed form functions, that include all those
that occur "in nature", are products of integer powers of terms of
the form 

$$
  (q)_{a_1 k_1 + a_2 k_2 + ... + a_r k_r + c} \,, \, \,a_i  \, \,integers, 
$$

multiplied by any polynomial 
$P( q^{k_1} , ... , q^{k_r} , q)$
times $q$ to the power any quadratic form in the
$k_1 , ... , k_r$. For example
the q-binomial coefficients $(q)_n /( (q)_k (q)_{n-k} )$.
Such closed form functions are called, in [WZ3], \it
proper closed
form\rm

{\bf Theorem:}

$$
  a(n):= \sum_{k_1} ... \sum_{k_r} "q-NICE" ( n, k_1 , ... , k_r ) 
$$

is q-P-recursive, and one can find (fairly) fast the recurrence.
Here, by "q-NICE" we mean "proper closed form".

Shalosh and its colleague Sol Tre have recently[E-T] given a new
and very short proof of the Rogers-Ramanujan identity:

$$
 \sum_{k=0}^{\infty} {{q^{ k^2 }}\over{(q)_k }}  \,= \, \prod_{n=0}^{\infty} 
{{1} \over {(1- q^{5n+1} ) (1- q^{5n+4} )}} \, \, \,. 
\eqno(R-R)
$$      

Well, not really. It would be a great moment for computerkind
when Shalosh (or any of its brethren) will be able to
generate a proof for {\it an arbitrary} identity of Rogers-Ramanujan
type.
\footnote{$^7$}{
It turns out that this problem was the seed to Paul Cohen's
proof of the independence of the continuum
hypothesis. In his own words([A-A-R],p.50):
"Because of my interest in number theory, however, I did become
spontaneously interested in the idea of finding a decision procedure for
certain identities, such as the famous Rogers-Ramanujan identity. I
thought that a procedure might exist analogous to, let's say, checking
an identity in algebra between polynomials. There are various famous
identities involving formal power series." (...) "I saw that the first
problem would be to develop some kind of formal system and then make an
inductive analysis of the complexity of the statements. In a remarkable
twist this crude idea was to resurface in the method of 'forcing' that I
invented in my proof of the independence of the continuum hypothesis."
}
There is no way that, today, Shalosh can prove (R-R) directly,
since both left side and right side have no parameters to spare.
What Shalosh {\it can}  prove is a more {\it general}
(and hence {\it easier}) identity, stated (and,
as it so happened, also first proved) by the human George
Andrews (see [E-T]):

$$
 \sum_{k=0}^{n} {{q^{ k^2 } (q;q)_{\infty} } \over {(q)_k (q)_{n-k} }}  \,= \,  \sum_{j= - n }^{n} {{(-1)^j q^{ (5 j^2 + j)/2 } (q;q)_{\infty} } \over {(q)_{n-j} (q)_{n+j} }}  \, \,. 
\eqno(R-R-finite)
$$    

Shalosh and Sol also had to prove, and did prove, the following
finite identity:

$$
 {{( q^5 ; q^5 )_{\infty} ( q^2 ; q^5 )_n ( q^3 ; q^5 )_n} \over { (q;q)_{\infty} }} \,= \, \sum_{j=-n}^{n} (-1)^j q^{(5 j^2 +j)/2}  [  { 2n \atop n+j }  ]_{q^5} {{( q^5 ; q^5 )_{\infty} } \over {(q;q)_{\infty}}} \, \, \,. 
\eqno(q-binomial)
$$   

The original Rogers-Ramanujan identity follows immediately upon
letting $n \rightarrow \infty$ in the above two shaloshable identities.

What's happening here? Shalosh {\it cannot} prove an identity
$a=b$ directly, so we need a human to conjecture a {\it finite form}
$A(n)=B(n)$, which is shaloshable, and such that
$A( \infty ) =a$, and $B( \infty ) =b$. In the R-R case, in fact,
the human had to conjecture {\it two} finite identities

$$
  A(n)=C(n) \, \, \, \,,B(n)=D(n) \, \, \,, 
$$

such that $C( \infty ) = D( \infty )$ and $A( \infty ) =a  \,, \, B( \infty )=b$. 
It might be that {\it every}
identity of "Rogers-Ramanujan" type

$$
  \sum_{k=0}^{\infty} t(k) \,= \, \sum_{k=0}^{\infty} s(k) \, \,, 
$$

or

$$
  \sum_{k=0}^{\infty} t(k) \,= \, \prod_{k=0}^{\infty} Rational(q, q^k  ) \, \,, 
$$

where both $t(k)$ and $s(k)$ are "nice"
(i.e. $t(k+1)/t(k)$ and $s(k+1)/s(k)$ are rational functions
in $( q^k , q)$) has corresponding "finite forms"
which are, of course, shaloshable. Even if this is not the
case in general, or if it is, but it's too hard to prove,
it would be interesting to develop heuristics for
"guessing" possible finite forms, which would then be routinely
provable.

Going back to the ordinary case, the hypergeometric identity ([vdP])

$$
 \sum_{n=1}^{\infty} {{1}\over{ n^3 }} = {{5}\over {2}} \sum_{n=1}^{\infty} {{(-1)^{n-1}} \over {n^3  (  {2n \atop n}  ) }} \, \,, 
\eqno(Apery)
$$        

is not directly shaloshable, but the "finite form"

$$
  \sum_{n=1}^{N} {{1}\over{ n^3 }} = {{5}\over {2}} \sum_{n=1}^{N} {{(-1)^{n-1}} \over {n^3  (  {2n \atop n}  ) }} + \sum_{k=1}^{N} {{(-1)^k} \over {2 k^3  (  {N+k \atop k}  )             (  {N \atop k}  )   }} \, \,, 
$$

which immediately implies it by taking $N \rightarrow \infty$, is shaloshable.

The complete elliptic integral of the first kind $K(k)$ is nothing
but ${}_2 F_1 ( 1/2,1/2 \,; \,1 \,; \, k^2 )$. It follows
that the "exact evaluations" (see [S-C]; [B-B], p. 298) at
the so called "singular values" are just certain infinite
hypergeometric series that happen to be expressed in terms of
$\Gamma$'s at rational points. I conjecture that all these are
just "tips of icebergs" of finite, shaloshable identities.
To obtain the infinite series corresponding to the $K(k)$ of
interest, one would have, of course, to use Carlson's
theorem (e.g.[Ba],p. 36ff), but this is very standard. For example,
the evaluations of the third singular value $K( k_3 )$,

$$
  K( \sqrt 2 ( \sqrt 3 -1 ) / 4 ) = {{3^{1/4} \Gamma ( 1/3)^3} \over { 2^{7/3} \pi }} \, \,, 
$$

is obtained by "plugging" $n= -1/2$ in (the non-terminating
extension of) the following shaloshable identity:

$$
  {}_2 F_1   ( {  { -n, 3n+2} \atop n+3/2 } ; ( \sqrt 3 +2)/4   )  \,= \, {{(3/2)_n}\over{(4/3)_n}} (-4/ 3 \sqrt 3 )^{n \, \, \,}. 
$$

$K( k_1 )$, $K( k_2 )$, and $K( k_4 )$ also
have terminating versions. Shalosh, and its
bigger siblings D.U.King and Ralbag, are now trying to find
terminating versions of further evaluations, and also
of Ramanujan's $(1/99)^4$ famous formula for $1/ \pi$.

{\bf The Next Ten Years of IS}

IS should not be confined to any one kind of identities. The
reason that I talked so much about hypergeometric identities is
merely personal. We should try and find other kinds of identities
that can be made shaloshable, either in principle, or better still,
in practice. 

Another worthy project, alluded to above, is to make shaloshable
as wide as possible a class of rational function identities that
will include the Good identity and its various analogs given by
Gustafson and Milne[Gu-Mi]. In [Z6] I give Lagrange interpolation
proofs, in the spirit of Good[Go] and Gustafson and Milne [Gu-Mi], of
several "fancy" formulas that arise in representation theory and other
parts of ("advanced", "graduate level") algebra. It would be nice
to make it all shaloshable.

Gustafson and Milne (e.g. [Gu],[Gu-Mi],[Mi]) are 
pursuing an ambitious
and impressive program of finding and proving {\it multi-variate}
hypergeometric identities with an {\it arbitrary} number of
sigmas (e.g.[Mi],[Gu]). Now for each {\it fixed} number
of sigmas their identities are shaloshable. For {\it fixed=1,2,3}
{\it in practice\rm
, but for \it
fixed $>$ 5} probably only 
{\it in principle}. But, please wait a minute! Computers and
Humans should not compete against each other, but COOPERATE.
One of the most fundamental identities in this theory, that
was the starting point for Milne's and Gustafson's work, is
Holman's [Ho] $U(N)$ generalization of Gauss's ${}_2 F_1 (1)$
identity. I let Shalosh find WZ proofs for $N=1, 2, 3$ and
THEY WERE GORGEOUS, and looked very much alike. So any
human could see the pattern and formulate a general WZ proof,
valid for any $N$. Only now the resulting "purely routine"
rational function identity of the multi-variate generalization([WZ3])
of the Meta-theorem is no longer
routine at all, since now we have a rational function identity
involving a {\it general} (arbitrary) number of variables and terms.
Although not routine (at present), it was nevertheless an easy human
exercise in using Lagrange interpolation (see [WZ3]). I am almost sure
that it is possible to give WZ proofs to all the multi-variate
hypergeometric identities of Gustafson and Milne. Of course,
{\it discovering} (i.e. conjecturing)
the identities at the first place is a completely different matter,
for which one needs human ingenuity and insight.
Other multi-variate
identities one may want to WZ-ize are the beautiful multi-variate
extension of
Foata and Garsia [F-G] of the Mehler formula, the Foata-Strehl
extension of the Hille-Hardy formula [F-S], and Strehl's[St] many
beautiful new multi-variate formulas given in his impressive
{\it habilationsschrift}.

A big {\it terra incognita} is a WZ approach to \it
Gaussian Sum Analogs \rm
of hypergeometric and Barnes-type identities. 
The first to prove such an analog was Anna Helversen-Pasotto[He],
which was a true landmark. Today this field is very active (e.g. [Gr-St])
and so far I don't see how to WZ-ize it.

The quintessential holonomic sequence is $n!$. But what about
(n!)!, ((n!)!)!, and so on. Perhaps one should define a whole
hierarchy of "generalized holonomic functions". A function
is 0-holonomic if it's a rational function. It's 1-holonomic
if it's a solution of a linear recurrence equation whose coefficients are
{\it 0-holonomic functions} (i.e. rational functions). So
one can define {\it r-holonomic} functions as solutions of
linear recurrence equations whose coefficients are
$(r-1)-$holonomic functions. So much for single variable.
For several variables, we would need some technical
conditions to avoid pathologies. It would be interesting
to develop a theory of identities for these higher holonomic
functions.

G\"odel and Turing (and later Hartmanis, Cook, and Karp)
taught us that computers {\it cannot} do
{\it everything}. However, I bet that they can do many many
more things than one imagines today. It would be fun to exploit
the great power of our machines in innovative ways, that will
show that they are far from just "dumb calculating jocks", but
equal, and in many respects, superior, colleagues.

{\bf REFERENCES}

[A-A-R] D.J. Albers, G.L. Alexanderson, and C. Reid, "\it
MORE
MATHEMATICAL PEOPLE\rm
", Harcourt Brace Jovanovich, Boston, 1990.

[A-Z] G. Almkvist and D. Zeilberger, \it
The method of differentiating
under the integral sign\rm
,
J. Symbolic Computation {\bf 10}(1990), 571-591.

[An] G.E. Andrews, \it
Plane Partitions V: the T.S.S.C.P.P
conjecture\rm
, J. Comb. Th. (ser. A), to appear.

[Ap] R. Ap\'ery,
\it
Irrationalite
de $\zeta (2)$ et $\zeta (3)$\rm
, Asterisque {\bf 61}(1979), 11-13.

[Ba] W.N. Bailey, "{\it GENERALIZED HYPERGEOMETRIC SERIES}", Cambridge
Math. Tract No. 32, Cambridge University Press, London and New York,
1935. (Reprinted:Hafner, New York, 1964).

[B-L-L] F. Bergeron, G. Labelle, and P. Leroux,\it
"COMBINATOIRE
ET STRUCTURES ARBORESCENTES"\rm
, a book in preparation.

[B-B] J.M. Borwein and P.B. Borwein, "{\it PI AND THE AGM}", John
Wiley, New York, 1987.

[deB] L. de Branges, {\it A proof of the Bieberbach conjecture},
Acta Math. {\bf 154}(1985), 137-152.

[D-V] M.P. Delest and G.X. Viennot, \it
Algebraic languages and
polyominoes enumeration\rm
, Theor. Comp. Sci. {\bf 34}(1984),
169-206.

[E1] S.B. Ekhad, \it
Short proofs of two hypergeometric summation formulas 
of Karlsson\rm
,
Proc. of the Amer. Math. Soc. {\bf 107}(1989),1143-1144.

[E2]  \_\_\_\_\_\_\_, {\it A very short proof of Dixon's theorem},
J. Comb. Theo. Series A {\bf 54}(1990), 141-142.

[E3] \_\_\_\_\_\_\_\_, \it
A one-line  proof of the Habsieger-Zeilberger 
$ G_2 $ constant term identity\rm
, J. Comput.
Appl. Math. {\bf 34}(1991), 133-134.

[E4] \_\_\_\_\_\_\_, \it
Short Proof Of A "Strange" Combinatorial Identity 
Conjectured by Gosper\rm
, Discrete Math, to appear.

[E5] \_\_\_\_\_\_, \it
A Short, Elementary, and Easy, WZ proof of the Askey-Gasper
inequality that was used by de Branges in his proof of the
Bieberbach conjecture\rm
, this issue.

[E-T] S. B. Ekhad and S.Tre,
\it
A purely verification proof of the first Rogers-Ramanujan
identity\rm
, J. Comb. The. Ser. A {\bf 54}(1990), 309-311.

[E-Z] S.B. Ekhad and D. Zeilberger,
{\it A 21st century proof of Dougall's hypergeometric sum identity},
J. Math. Anal. Appl. {\bf 147}(1990), 610-611. 

[Fo] D. Foata,\it
 Combinatoire des identites sur les
polynomes orthogonaux\rm
,in "Proc.Inter.Congress of Math. [Warsaw,
Aug. 16-24, 1983]", 1541-1553, Varsovie, 1983.

[F-G] D.Foata and A.Garsia, \it
A combinatorial approach of the Mehler
formulas for Hermite polynomials. In "\it
Relations between
combinatorics and other branches of mathematics,Columbus, 1978\rm
",
163-179, Amer. Math. Soc., Providence, 1979.

[F-S] D. Foata nd V. Strehl, \it
Une extension multiline\*'aire
de la formule d'Erde\*'lyi pour les produits de fonctions 
hyperge\*'metriques confluentes\rm
, C.R. Acad. Sc. Paris,
{\bf 293}(1981), 517-520.

[Ga-Go] F. Garvan and G. Gonnet, 
\it
Macdonald's constant term conjectures for the
exceptional root systems\rm
, Bulletin (new series) of the Amer.
Math. Soc. {\bf 24}(1991), 343-347.

[Go] I.J. Good,\it
Short proof of a conjecture bt Dyson,\rm
J. Math. Phys. {\bf 11}(1970), 1884.

[Gr-St] J. Greene and D. Stanton, \it
A character sum evaluation and
Gaussian hypergeometric series\rm
, J. Number Theo. {\bf 23}(1986),
136-148.

[Gu] R.A. Gustafson, \it
A generalization of Selberg's beta
integral\rm
, Bulletin (new series) of the Amer. Math. Soc.
{\bf 22}(1990), 97-105.

[Gu-Mi] R.A. Gustafson and S.C. Milne, \it
Schur
functions, Good's identity, and hypergeometric series well poised in
SU(n)\rm
, Adv. in Math. {\bf 57}(1985), 209-225.

[He] A. Helversen-Pasotto, \it
L'identit\'e de Barnes pour les corps
finis\rm
, C.R. Acad. Sci. Paris, Se\*'rie A, {\bf 286}(1978),
297-300.

[Ho] W.J. Holman III, \it
Summation theorems for hypergeometric
series in $U(n)$\rm
, SIAM J. Math. Anal. {\bf 11}(1980), 523-532.

[Ma] I.G. Macdonald, {\it Some conjectures for root systems},
SIAM J. Math. Anal. {\bf 13}(1982), 988-1007.

[Mi] S.C. Milne, \it
A q-analog of the Gauss Summation Theorem
for hypergeometric series in U(n)\rm
, Adv. Math. {\bf 72}(1988) 59--131. 

[Pa] J.A. Paulos,{\it "BEYOND NUMERACY, ruminations of a numbers man"},
Alfred A. Knopf, New York, 1991.

[vdP] A. van der Poorten, \it
A Proof that Euler missed..., Ap\'ery's
proof of the irrationality of \rm $\zeta (3)$, Math. Intel.
{\bf 1}(1979), 195-203.

[Sa] B. Sagan,"{\it THE SYMMETRIC GROUP}", Wadsworth \& Brooks/Cole,
Pacific Grove, California, 1991.

[S-C] A. Selberg and S. Chowla, "{\it On Epstein's zeta function}", 
J. Reine Ang. Math. {\bf 227}(1967), 86-110.

[St] V. Strehl, "\it
ZYKEL-ENUMERATION BEI LOCAL-STRUKTURIEN 
FUNKTIONEN\rm
", {\it Habilationsschrift}, Universita\*:t
Erlangen-N\"urnberg, Germany, 1990.

[Va] R.S. Varga, "SCIENTIFIC COMPUTATION ON MATHEMATICAL PROBLEMS
AND CONJECTURES", CBMS-NSF Regional Conference Series in Applied
mathematics {\bf 60}, SIAM, Philadelphia, 1990.

[V] P. Verbaeten, \it
The automatic construction of pure recurrence
relations\rm
, Proc. EUROSAM '74, ACM-SIGSAM Bulletin {\bf 8}(1974),
96-98.

[WZ1] H.S. Wilf and D. Zeilberger, \it
Towards computerized 
proofs of identities\rm
,
Bulletin of the Amer. Math. Soc. {\bf 23}(1990), 77-83.

[WZ2]\_\_\_\_\_\_\_\_\_\_, \it
Rational functions certify combinatorial
identities\rm
, J. Amer. Math. Soc. {\bf 3}(1990), 147-158.

[WZ3]\_\_\_\_\_\_\_\_\_\_,\it
A general theory of multi-variate hypergeometric
identities\rm
, in preparation.

[Z0] D. Zeilberger, \it
Sister Celine's technique 
and its generalizations, J. Math. Anal. Appl. {\bf 85}(1982), 114-145.

[Z1] \_\_\_\_\_\_\_, \it
A Holonomic systems approach to special functions
identities\rm
, J. of Computational and Applied Math. {\bf 32}(1990),
321-368.

[Z2] \_\_\_\_\_\_\_\_, \it
 A Fast Algorithm for proving terminating hypergeometric
identities\rm
, Discrete Math {\bf 80}(1990), 207-211.

[Z3] \_\_\_\_\_\_\_\_, {\it The method of creative telescoping}, 
J. Symbolic Computation {\bf 11}(1991), 195-204.

[Z4] \_\_\_\_\_\_\_\_, {\it Closed Form (pun intended!)}, 
to appear in: "Special volume in memory of Emil Grosswald", M. Knopp,
ed., Contemporary Mathematics, AMS.

[Z5] \_\_\_\_\_\_\_\_\_, \it
Three recitations on Holonomic Systems and 
Hypergeometric Series\rm
, Proceeding of the S\'eminaire
Lotharingien de combinatoire {\bf 24}, IRMA, Strasbourg, to appear.

[Z6] \_\_\_\_\_\_\_\_\_, \it
Plain (Lagrange interpolation) proofs of Fancy
(representation theory) formulas\rm
, in preparation.

July 25, 1991
\end




