  
%wordy.tex:A plain TeX file of a 2-page paper by D. Zeilberger
%begin macros
\def\M{\cal M}
\def\bar1{\overline}
\def\mod{\mathop{\rm mod} \nolimits}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\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\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
%end macros
\bf
\centerline
{A WORDY PROOF OF A COMBINATORIAL LEMMA THAT AROSE IN OPERATOR THEORY}
\rm
\bigskip
\centerline{ {\it Doron ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. 
{\eighttt zeilberg@math.temple.edu \break
http://www.math.temple.edu/\Tilde zeilberg \quad
 ftp://ftp.math.temple.edu/pub/zeilberg} \quad .
\break
Supported in part by the NSF. Aug. 2, 1995.
This paper is exclusively published in the above http and ftp sites.
} 
}
 
Albert Einstein used to be amazed how effective mathematics is
in science. Myself, I am amazed how effective combinatorics is in
mathematics. Especially fruitful is the
`formal language approach' of {\it notre bon Ma\^itre}, Marco Sch\"utzenberger,
pursued so vigorously and successfully by the
{\it \'Ecole Bordelaise} (see [B] and references thereof).
 
Recently, Baillon and Bruck[BB] proved a long-standing conjecture in
operator theory, by reducing it to a hypergeometric identity that
they proved using the package EKHAD\footnote{$^2$}
{\eightrm Available from the
http and ftp sites given in footnote 1. Once you downloaded it
into your directory, get into Maple, and type:
{\eighttt read EKHAD;},  and follow the instructions given there}
(accompanying the forthcoming book [PWZ],)
 They asked for
a `computer-free' proof. Such a proof was later given by
Peter Paule[P]. However, the reduction of their result to the identity
proved by EKHAD and Paule required considerable human effort on their part.
In this note I will give a much shorter (and purely human!) proof
by playing with (Motzkin\footnote{$^3$}
{\eightrm It is interesting that often political leaders
begat  combinatorialists. 
Theodore Motzkin is
the son of the Zionist leader Leo Motzkin (that has a town
in Israel named after him, where, incidentally, I grew up).
Other examples (of the sons) are Michel Mend\`es-France, Robin Wilson and
Eri Jabotinsky.}) words, dear to Viennot and his disciples.
 
{\bf Proposition([BB]):}  Let $c(m,n)$ be defined by
$c(m+1,m)=0$, $(m \geq 0)$, $c(0,n)=1$, $(n \geq 0)$,
and for $1 \leq m \leq n$, by the recurrence
$$
c(m,n)= \mu c(m-1,n) + \mu c(m,n-1) + (1- 2 \mu)c(m-1,n-1) \quad ,
$$
then the generating function of the `diagonal',
$$
\psi(t):=\sum_{m=0}^{\infty} c(m,m) t^m \quad,
$$
is given by
$$
\psi(t)= 1+ {{\sqrt{1+ {{4(1-\mu)\mu t} \over {1-t}}} - 1}
\over {2 \mu}} \quad  .
$$
 
{\bf Proof:}  Consider all words $w$ in the alphabet $\{ N,E,D\}$.
For any word $w$ let $y(w)$ be the number of $N$s plus the number
of $D$s and let $x(w)$ be the number of $E$s plus the number of $D$s.
Let $\M$ be the set of words $w= l_1 l_2 \dots l_r$ such for
any prefix $w_i:= l_1 l_2 \dots l_i$ ($1 \leq i \leq r$) one has
$y(w_i) \geq x(w_i)$. Let $\M$$(m,n)$ be the subset of $\M$ for which
$x(w)=m$ and $y(w)=n$.
 
Let the {\it weight} of the letters $N$ and $E$ be $\mu$, and the
weight of the letter $D$ be $1-2 \mu$. Introduce two
weights on the words of $\M$. The normal weight,
$weight(w)$ is simply the product of the weights of all the letters.
For example $weight(NNDE)=\mu\mu(1-2\mu)\mu=\mu^3(1-2\mu)$.
The modified weight, $weight'$ is as before, {\it except} that the initial
string of $N$s is given weight $1$. 
For example $weight'(NNNDEDE)=1^3 \cdot (1-2\mu)\mu(1-2\mu)\mu$
$=(1-2\mu)^2\mu^2$. Let
$$
C(m,n):=\sum_{w \in \hbox{$\M$$(m,n)$}} weight'(w) \quad .
$$
Since, for $n\geq m>0$, we have 
$\M$$(m,n)$=$\M$$(m-1,n)E$ $\cup$ $\M$$(m,n-1)N$ $\cup$ $\M$$(m-1,n-1)D$, and
$\M$$(m+1,m)$ is the empty set, while $\M$$(0,n)$ consists of
the single word $N^n$, taking $weight'$, we see that
$c(m,n)=C(m,n)$.
 
Let $\bar1{\M}$ be the set of all words $w$ in $\M$ such that
$x(w)=y(w)$, in other words (sic!), the set of all words
in $\M$ with as many $Ns$ as $Es$. 
Let $WEIGHT(w):=t^{x(w)}weight(w)$, and
$WEIGHT'(w):=t^{x(w)}weight'(w)$. Since the `syntax' of $\bar1{\M}$ is
given by:
$$
\bar1{\M}= \{empty \quad word\} \cup D\,\bar1{\M} \cup 
N\,\bar1{\M}\,E\,\bar1{\M} \quad,
$$
taking $WEIGHT$ and $WEIGHT'$ respectively yields that
$\phi(t):=\sum_{w \in \bar1{\M}} WEIGHT(w)$ and
$\psi(t):=\sum_{w \in \bar1{\M}} WEIGHT'(w)$ satisfy the equations
$$
\phi(t)= 1+ t(1-2\mu)\phi(t) +\mu^2 t \phi(t)^2 \quad ,
$$
$$
\psi(t)= 1+ t(1-2\mu)\phi(t) +\mu t \psi(t) \phi(t) \quad .
$$
Now use the second equation to express $\phi(t)$ in terms
of $\psi(t)$, plug into the first equation, clear denominators,
and solve the resulting quadratic equation in $\psi(t)$, getting
the expression for $\psi(t)$ claimed in the proposition. \halmos
 
{\bf Remark:} For their application, Baillon and Bruck 
were only interested in the asymptotics of $c(m,m)$, which is
just as easily derived from the expression in the
proposition above (which is Th. 5.5 in [BB]) as from their
integral representation (Th. 6.1 there). However, one can easily
prove (albeit using EKHAD's services) that these are
equivalent, by typing (in EKHAD):\break
{\tt AZpapd(sqrt(1+4*mu*(1-mu)*t/(1-t))/t**(m+2),t,m);} \break
and {\tt AZpapd(sqrt(t/(1-t))*(1-4*mu*(1-mu)*t)**m,t,m);}
\medskip
{\bf References}
 
[BB] J.-B. Baillon and R.E. Bruck, {\it The rate of Asymptotic
Regularity is $O(1/\sqrt{n})$}, preprint. Available
from {\tt bruck@mtha.usc.edu}. 
 
[B] M. Bousquet-M\'elou, ``{\it q-\'Enum\'eration de polyominos convexes}'',
Publications de LACIM, UQAM, Montr\'eal, 1991.
 
[P] P. Paule, available from {\tt peter.paule@risc.uni-linz.ac.at}. 
 
[PWZ] M. Petkovsek, H.S. Wilf, and D.Zeilberger, {\it ``A=B''},
A.K.Peters, to appear.
 
\bye
 
 
 
 
 
 
