<s>[INST] Flip a coin 5 times. What is the probability that heads never occurs twice in a row? 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
 [/INST] Let head be represented by 0 and tail by 1. Then a sequence of heads and tails can be represented by a binary number.
For 2 tosses ($n = 2$), the possible sequences are:
00
01
10
11

There are $2^2$ total possible sequences and among them the number of sequences where heads never occurs twice in a row is 3. So for $n = 2$, the probability of heads never occurs twice in a row is $P_2=\frac{3}{4}$.
Similarly, for $n = 3$, the sequences are:
000
001
010
011
100
101
110
111

Again there are $2^3$ total possible sequences, and 5 of them with heads never occurs twice in a row. So $P_3=\frac{5}{8}$.
To find the general formula for calculating $P_n$, lets make the following observation:


*

* When adding a new most significant digit to get the binary numbers of $n$ digits, for example, to expend the numbers from $n=2$ to $n=3$ above, we make 2 copies of all of the binary numbers of $n-1$ digits, add $0$s to left of the top copy and $1$s to the bottom copy.

*The top quarter of the new binary numbers all has two $0$s at the beginning.

*The second quarter of the new binary numbers has the same number of sequences, where heads never occurs twice, as that of $n-2$, that is $2^{n-2}P_{n-2}$.

*The bottom half of the new binary numbers has the same number of sequences, where heads never occurs twice, as that of $n-1$, that is $2^{n-1}P_{n-1}$.


Based on these observations we have:
$$
P_n = \frac{2^{n-2}P_{n-2} + 2^{n-1}P_{n-1}}{2^n} = \frac{\frac{1}{2}P_{n-2} + P_{n-1}}{2}
$$
Using this recursive formula, we get:
$$
P_4=\frac{\frac{1}{2}P_2+P_3}{2}=\frac{\frac{1}{2}\frac{3}{4}+\frac{5}{8}}{2}=\frac{1}{2}
$$
$$
P_5=\frac{\frac{1}{2}P_3+P_4}{2}=\frac{\frac{1}{2}\frac{5}{8}+\frac{1}{2}}{2}=\frac{13}{32}
$$
$$
P_6=\frac{\frac{1}{2}P_4+P_5}{2}=\frac{\frac{1}{2}\frac{3}{4}+\frac{5}{8}}{2}=\frac{21}{64}
$$
</s>