# A Proof by Game

Problem

Prove

\frac{1}{4}+\frac{1}{8}+\frac{2}{16}+\frac{3}{32}+\frac{5}{64}+\ldots=1.

Solution

Let's play a game, a solitaire in fact. Place a token at Start. Toss a fair coin. Advance 2 steps on HEADS and 1 on TAILS.

Summing up the probabilities of reaching End in exactly n turns, n\ge 2, yields the series.

Indeed, there is just 1 possibility (TAILS, HEADS) to reach End after two tosses.

There is only 1 possibility (HEADS, TAILS, HEADS) to reach the End after three tosses.

Now note that

• any successful (i.e., leading to End) series of tosses must terminate in the pair of outcomes TAILS, HEADS.
• there are just two short ways to stay at the Start: throwing TAILS twice (probability of \frac{1}{4}) and throwing HEADS once (probability \frac{1}{2}).
• if a sequence T_1,T_2,\ldots ,T_{n-2},TAILS,HEADS terminates in n tosses, where T_i is the result of the i-th toss, then the sequence T_1,T_2,\ldots ,T_{n-2},HEADS,TAILS,HEADS terminates in n+1 while the sequence T_1,T_2,\ldots ,T_{n-2},TAILS,TAILS,TAILS,HEADS terminates in n+2 tosses.

It follows that, if S_n is the number of ways to succeed in the game in exactly n moves, then we have a Fibonacci identity:

S_n = S_{n-1}+S_{n-2}.

On the other hand, if P_n is the probability of success in exactly n moves, then

P_n = \frac{P_{n-1}}{2}+\frac{P_{n-2}}{4}.

The two identities furnish an inductive proof of

Proposition

For n \ge 2,

P_n = \frac{F_{n-2}}{2^n},

where F_k are Fibonacci numbers defined recursively via

F_0 = F_1 = 1
F_k = F_{k-1}+F_{k-2}, k\ge 2.

References

1. Kay P. Litchfield, Mathematics Magazine, Vol. 67, No. 4 (Oct. 1994), 281