A New Proof that there are 2^{n} Possible Outcomes on Tossing a Coin n Times

Doron ZEILBERGER^{1}

A short proof is not as satisfying as a long one. A good mathematical proof should do much more than just prove the theorem. It should amuse, instruct, and satisfy our deeper love of knowledge, which is much more important than our mere 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} … w_{n} | w_{i} = H or T }

equals 2^{n} is not quite satisfactory. It is based on the very superficial ‘structure theorem’: W_{n} = W_{n−1} × {H, T } which immediately implies that |W_{n}| = |W_{n−1}| · 2, which immediately implies |W_{n}| = 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

\binom{2n − 2k}{n − k}\binom{2k}{k} .

The present proof is in the style and spirit of our good master, Marco Schützenberger.

Let H := +1 and T := −1. Define the two sets

C_{n} := {w ∈ W_{n} | ∑_{j=1}^{i} w_{j} ≥ 0 , 1 ≤ i < n , and ∑_{j=1}^{n} w_{j} = 0 } ,

the famous Dyck words (or Catalan paths), and

U_{n} := {w ∈ W_{n} | ∑_{j=1}^{i} w_{j} ≥ 0 , 1 ≤ i ≤ n } .

Let

W := ∪_{n=0}^{∞} W_{n} , C := ∪_{n=0}^{∞} C_{n} , U := ∪_{n=0}^{∞} U_{n} .

For each element w of W, we will define its weight to be weight(w) := z^{n}, where n is its length (i.e. w ∈ W_{n}). The main theorem of this paper is equivalent to:

α(z) := ∑_{w∈W} weight(w) = \frac{1}{1 − 2z} ,

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA.

E-mail:zeilberg@math.temple.edu ; WWW: http://www.math.temple.edu/~zeilberg . Supported in part by the NSF. November 16, 1995.

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 HuT v, where u and v are shorter members of C. Hence, we have the ‘syntax’:

C = empty ∪ HCT C .

Since weight(HuT v) = z^{2}weight(u)weight(v), we have that the total weight,

ψ(z) := ∑_{w∈C} weight(w) ,

satisfies the quadratic equation

ψ(z) = 1 + z^{2}ψ(z)^{2} .  (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 ∈ U, or can be written as HuT v, where u ∈ C and v ∈ U. Hence, taking C as given, the language U has the syntax:

U = empty ∪ HU ∪ HCT U .

Taking weight, yields that

ϕ(z) := ∑_{w∈U} weight(w) ,

satisfies the equation

ϕ(z) = 1 + zϕ(z) + z^{2}ψ(z)ϕ(z) .  (eq2)

Let C̄ and Ū 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 ∈ W is either the empty sequence, or can be written as Hu, with u ∈ U, or T ū, with ū ∈ Ū, or HuT w′, with u ∈ C, and w′ ∈ W, or T ūHw′, with ū ∈ C̄, and w′ ∈ W. Hence W has the following syntax:

W = empty ∪ HU ∪ T Ū ∪ HCT W ∪ T C̄HW .  (T akhbir)

Taking, weight, gives the equation:

α(z) = 1 + 2zϕ(z) + 2z^{2}ψ(z)α(z) .  (eq3)

Solving the quadratic equation (eq1), then using (eq2) to get an expression for ϕ(z), and then using (eq3) to get an expression for α(z), and simplifying, yields that indeed α(z) = (1 − 2z)^{−1}.

To get Sparre Andersen’s result, define a new weight, poids, as follows. First, for w ∈ W_{n}, let

up(w) := #{1 ≤ i ≤ n | ∑_{j=1}^{i−1} w_{j} ≥ 0 and ∑_{j=1}^{i} w_{j} ≥ 0 } ,

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)} ,

where n is the length of the word i.e. w ∈ W_{n}. Obviously poids(C) = ψ(zt), poids(U) = ϕ(zt), while poids(C̄) = ψ(z), poids(Ū) = ϕ(z). Taking poids in Eq. (T akhbir), yields that,

β(z, t) := ∑_{w∈W} poids(w) ,

satisfies the equation:

β(z, t) = 1 + zϕ(z) + ztϕ(zt) + (z^{2}ψ(z) + (zt)^{2}ψ(zt))β(z, t) .  (eq4)

Solving this linear equation for β, taking the even part, with respect to z:

β̃(z, t) := \frac{β(z, t) + β(−z, t)}{2} ,

and simplifying, yields that

β̃(z, t) = (1 − 4z^{2})^{−1/2}(1 − 4z^{2}t^{2})^{−1/2} .

Since

(1 − 4z^{2})^{−1/2} = ∑_{m=0}^{∞} \binom{2m}{m}z^{2m} ,

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

β̃(z, t) = (1 − 4z^{2})^{−1/2} · (1 − 4z^{2}t^{2})^{−1/2} ,

is indeed

\binom{2n − 2k}{n − k}\binom{2k}{k} ,

as proved first by Sparre Andersen.

A short Maple program sparre that carries all the routine verifications of this paper, is available

by anonymous ftp to ftp.math.temple.edu, in directory /pub/zeilberg/stam. The output file

outsparre can also be found there.

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

(hijab@math.temple.edu http://www.math.temple.edu/~hijab). His talk, intended for under-

graduates, 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. References

[F] W. Feller, An Introduction to Probability Theory and Its Applications, volume 1. Wiley, 1950; third edition, 1968.

[H] O. Hijab, A Course in Real Analysis, Springer, to appear.