A fair coin is tossed n times. What is the probability that no two consecutive heads appear? A fair coin is tossed n times. What is the probability that no two consecutive heads appear?

If a coin is tossed, for example, 10 times:

There are 2^10 = 1024 total possible outcomes of 10 tosses.

Now we count the number of possible outcomes with no two consecutive heads. Let x_n be this number for n tosses - we wish to find x_10. For n > 2, the string of tosses must fall into one of two disjoint categories:

(i) tosses ending with a tail

(ii) tosses ending with a tail then a head

(i. e. tosses ending with a head then a head is impossible)

Given that the first n-1 or n-2 tosses must also have no two consecutive heads, we sum the number of possibilities of case (i) and (ii) and find

x_n = x_{n-1} + x_{n-2}.

We also easily see that x_1 = 2, x_2 = 3. From the above recurrence we can compute x_n as terms of the Fibonacci sequence until x_10 = 144.

Since the coin is unbiased all these possibilities are equally likely and the answer is 144/1024 = 9/64.