 
  
%toss.tex: A plain TeX file of the paper
%`A New Proof that there 2^n possible outcomes on tossing a coin n times`
%outputs 3.2 pages
%begin macros
\def\C {{\cal C}}
\def\U{{\cal U}}
\def\W{{\cal W}}
\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 New Proof that there are 
$2^n$ Possible Outcomes on Tossing a Coin $n$ Times}
\rm
\bigskip
\centerline{ {\it Doron ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. \hfill \break
E-mail:{\eighttt  zeilberg@math.temple.edu }  ;
WWW: {\eighttt http://www.math.temple.edu/\Tilde zeilberg } .
Supported in part by the NSF. November 16, 1995.
 } \quad 
\break
} 
 
A short proof is not as satisfying as a long one.
A good mathematical proof should do much more than just {\it prove}
the theorem. It should amuse, instruct, and satisfy
our deeper love of knowledge, which is much more important than
our mere {\it desire} to know whether the theorem is true.
 
I find that the standard proof that the number of elements of
$$
\W_n:=\{w=w_1 \dots  w_n \,\,\vert \,\,w_i=H \quad or \quad T \}
$$
equals $2^n$ is not quite satisfactory. It is based on the
very superficial `structure theorem': $\W_n=\W_{n-1} \times \{H,T\}$
which immediately implies that $\vert \W_n \vert=\vert \W_{n-1}\vert \cdot 2$,
which immediately implies $\vert \W_n \vert =2^n$, by induction.
 
In this note I will give a new proof of this famous fact, that is based
on a much deeper and more interesting 
structure that the set of sequences of Heads and Tails possesses.
As a bonus, we will also get a new proof of Erik Sparre Andersen's
famous `arcsine' result ([F]), that the number of ways of
tossing a coin $2n$ times, and having at least as many Heads as
Tails at exactly $2k$ of these tosses, is
$$
{{2n-2k} \choose {n-k}}{{2k} \choose {k}} \quad.
$$
 
The present proof is in the style and spirit of our good master,
Marco Sch\"utzenberger.
 
Let $H:=+1$ and $T:=-1$. Define the two sets
$$
\C_n:=\{ w \in \W_n \,\,\,\vert \,\,\,\sum_{j=1}^i w_j \geq 0 \,\,, 
\,\, 1 \leq i < n \, ,
\quad and \quad \sum_{j=1}^n w_j =0 \,\,\} \quad ,
$$
the famous Dyck words (or Catalan paths), and
$$
\U_n:=\{ w \in \W_n \,\,\vert \,\,
\sum_{j=1}^i w_j \geq 0 \,\,,\, 1 \leq i \leq n \,\} \quad .
$$
 
Let
$$
\W:=\cup_{n=0}^{\infty} \,\W_n \quad ,\quad
\C :=\cup_{n=0}^{\infty} \,\C_n \quad ,\quad
\U:=\cup_{n=0}^{\infty} \, \U_n \quad .
$$
For each element $w$ of $\W$, we will define its {\it weight} to be
$weight(w):=z^n$, where $n$ is its length
(i.e. $w \in \W_n$). The main theorem of this
paper is equivalent to:
$$
\alpha (z):=\sum_{w \in \W} weight (w) = {{1} \over {1-2z}} \quad ,
$$ 
as can be seen by extracting the coefficient of $z^n$ from both sides.
 
It is readily seen (and well known) that any element $w$ of $\C$
is either the empty word (whose weight is $1$), or else can
be written as $HuTv$, where $u$ and $v$ are shorter members of $\C $.
Hence, we have the `syntax':
$$
\C  =empty \,\, \cup \,\, H\C  T \C  \quad .
$$
Since $weight(HuTv)=z^2 weight(u)weight(v)$, we have that the
{\it total weight},
$$
\psi (z):=\sum_{w \in \C } weight (w) \quad ,
$$ 
satisfies the {\it quadratic equation}
$$
\psi(z)=1+z^2\psi(z) \quad.
\eqno(eq1)
$$
 
It is also easy to see that every element $w$ of $\U$ is either
the empty word or can be written as $Hu$, where $u \in \U$,
or can be written as $HuTv$, where $u\in \C $ and $v \in \U$.
Hence, taking $\C $ as given, the language $\U$ has the syntax:
$$
\U = empty \quad \cup \,\,H\U \,\,\cup \,\, H\C T\U \quad .
$$
Taking weight, yields that
$$
\phi (z):=\sum_{w \in \U} weight (w) \quad ,
$$ 
satisfies the equation
$$
\phi(z)=1+z\phi(z)+z^2\psi(z)\phi(z) \quad .
\eqno(eq2)
$$
 
Let $\bar \C $ and $\bar \U$ be the reflections of $\C $ and $\U$ respectively,
where the $H$'s and $T$'s are interchanged. It is easy to see that
any element $w \in \W$ is either the empty sequence, or can be written
as $Hu$, with $u\in \U$, or $T\bar u$, with $\bar u\in \bar \U$,
or $HuTw'$, with $u \in \C $, and $w' \in \W$, or
$T\bar u Hw'$, with $\bar u \in \bar \C $, and $w' \in \W$. Hence
$\W$ has the following syntax:
$$
\W= empty \,\, \cup \,H\U \,\, \cup \,T \bar \U \,\cup \, H\C T\W \, \cup 
\, T\bar \C H \W \quad.
\eqno(Takhbir)
$$
Taking, $weight$, gives the equation:
$$
\alpha(z)=1+2z\phi(z)+2z^2\psi(z)\alpha(z) \quad .
\eqno(eq3)
$$
Solving the quadratic equation $(eq1)$, then using $(eq2)$ to get
an expression for $\phi(z)$, and then using $(eq3)$ to get an
expression for $\alpha(z)$, and simplifying, yields that indeed
$\alpha(z)=(1-2z)^{-1}$. \halmos
 
To get Sparre Andersen's result, define a new weight, $poids$, as follows.
First, for $w \in \W_n$, let
$$
up(w):=\# \{  1 \leq i \leq n \,\,\vert\,\, 
\sum_{j=1}^{i-1} w_j \geq 0 \quad and
\sum_{j=1}^{i} w_j \geq 0 \,\,\}\quad,
$$
the number of tosses for which it was not losing right before and 
right after it (assuming that you win and lose a dollar according
to whether you got $H$ or $T$). The new weight, $poids$, is defined
by:
$$
poids(w):=z^n t^{up(w)} \quad,
$$
where $n$ is the length of the word i.e. $w \in \W_n$.
Obviously $poids(\C )=\psi(zt)$, $poids(\U )=\phi(zt)$, while
$poids(\bar \C )=\psi(z)$, $poids(\bar \U )=\phi(z)$. Taking
$poids$ in Eq. $(Takhbir)$, yields that,
$$
\beta(z,t):=\sum_{w \in \W} poids(w) \quad ,
$$
satisfies the equation:
$$
\beta(z,t)=1+z\phi(z)+zt\phi(zt)+(z^2\psi(z)+(zt)^2\psi(zt))\beta(z,t) \quad.
\eqno(eq4)
$$
Solving this linear equation for $\beta$, 
taking the even part, with respect to $z$:
$$
\widetilde \beta(z,t) :={{\beta(z,t)+\beta(-z,t)} \over {2}} \quad ,
$$
and simplifying, yields that
$$
\widetilde \beta(z,t) =(1-4z^2)^{-1/2} (1-4z^2t^2)^{-1/2} \quad .
$$
Since
$$
(1-4z^2)^{-1/2}=\sum_{m=0}^{\infty} \,\, {{2m} \choose {m}} z^{2m} \quad ,
$$
we see that the number of ways of tossing a coin $2n$ times, and not
being at loss in $2k$ of them, i.e. the number of $w$ for which
$poids(w)=z^{2n}t^{2k}=z^{2(n-k)}(zt)^{2k}$, which is the coefficient
of $z^{2(n-k)}(zt)^{2k}$ in
$$
\widetilde \beta(z,t) =(1-4z^2)^{-1/2} \cdot (1-4z^2t^2)^{-1/2} \quad ,
$$
is indeed 
$$
{{2n-2k} \choose {n-k}} {{2k} \choose {k}} \quad ,
$$
as proved first by Sparre Andersen.
 
A short Maple program {\tt sparre} that carries all the routine
verifications of this paper, is available by
anonymous {\tt ftp} to {\tt ftp.math.temple.edu}, in directory
{\tt /pub/zeilberg/stam}. The output file {\tt outsparre} can also
be found there.
 
{\bf Thanks}
 
I was reminded about this beautiful result of Sparre Andersen
two days ago, when I attended a fascinating 20-minute
talk, about the arcsine law, by my colleague Omar Hijab \hfill\break
({\tt hijab@math.temple.edu  http://www.math.temple.edu/\Tilde hijab}).
His talk, intended for undergraduates, was part of the festivities
of the Temple University 
Math Day, organized by Hijab. I strongly recommend that
you read, and consider adopting, his excellent forthcoming
textbook [H], that contains,
among much other fascinating material, a discussion of the arcsine law.
 
{\bf References}
 
[F] W. Feller, {\it An Introduction to Probability Theory and Its 
Applications}, volume 1. Wiley, 1950; third edition, 1968.
 
[H] O. Hijab, {\it A Course in Real Analysis}, Springer, to appear.
 
\bye
