*Problem*

Prove

*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*:

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

The two identities furnish an inductive proof of

**Proposition**

For n \ge 2,

where F_k are Fibonacci numbers defined recursively via

**References**

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