Suppose I flip a coin $5$ times in a row. There are $2^5$ possible outcomes, i.e: HHHTH, HTTTT, HTHTH, etc. I want to know the probability that heads never occurs twice in a row.
I drew out $32$ events that can occur, and I found out that the answer was $\cfrac{13}{32}$. But I'm not sure how to do this generally, because say if the coin was flipped $20$ times in a row, I wouldn't write out $2^{20}$ possibilities.
Thanks
Best Answer
Let $a_n$ be the number of sequences of length $n$ that do not contain two consecutive heads.
Observe that any sequence of heads and tails of length one is permissible since we cannot obtain two heads in a row. Hence, $a_1 = 2$.
Any sequence of length two is permissible except HH. Hence, $a_2 = 2^2 - 1 = 3$.
We can write a recurrence relation for a sequence of length $n$. An admissible sequence of length $n$ that ends in heads must have a tails in the $(n - 1)$st position. Hence, any sequence of length $n$ that ends in heads corresponds to an admissible sequence of length $n - 2$ to which the sequence TH is appended. There are $a_{n - 2}$ such sequences. An admissible sequence of length $n$ that ends in tails is an admissible sequence of length $n - 1$ to which a tails is appended. There are $a_{n - 1}$ such sequences. Hence, we have the recurrence relation $$a_n = a_{n - 1} + a_{n - 2}$$ Thus, the number of admissible sequences of length $n$ is given by the recursion \begin{align*} a_1 & = 2\\ a_2 & = 3\\ a_n & = a_{n - 1} + a_{n - 2}, n \geq 3 \end{align*} Notice that $a_3 = 5$, $a_4 = 8$, and $a_5 = 13$. You may recognize these as Fibonaccci numbers. In particular, $a_n = F_{n + 2}$.
The desired probability is $$\frac{a_n}{2^n}$$