Problem:
A fair coin is to be tossed ten times. Let , in lowest terms, be the probability that heads never occur on consecutive tosses. Find .
Solution:
There are possible sequences of length that can be formed from the letters and . Let be the number of these sequences in which there are no adjacent occurrences of . The values and may be found by simply listing all possible outcomes for tosses of and coins respectively. For higher values of , we may find by using the recursion relation , which holds for any positive integer . This recursion relation is true because counts two distinct types of sequences: those with no consecutive 's that end with (there are of them) and those with no consecutive 's that end with (there are of these).
It follows that the values are Fibonacci numbers, so . Hence the probability of tossing a coin ten times and never having heads occur on consecutive tosses is and .
The problems on this page are the property of the MAA's American Mathematics Competitions