[Math] Number of ways to flip a coin 10 times with no consecutive heads

combinatoricsdiscrete mathematicsprobability

The problem statement is as follows: A fair coin is to be tossed $10_{}^{}$ times. Let $i/j^{}_{}$, in lowest terms, be the probability that heads never occur on consecutive tosses. Find $i+j_{}^{}$.

My solution was to consider the sequence of flips as a string of either [Head then Tail] or [Tail]. Let $x$ represent the number of [Head then Tail] and $y$ represent the number of [Tail]. Then $2x$ + $y$ = $10$.

Then I did casework for each value of $x$:

When $x = 0$ it is bijective to the number of arrangements of $AAAAAAAAAA$, which is $1$.

Then, when $x = 1$ it is bijective to the number of arrangements of $AAAAAAAAB$, which is 9 and so on…

The sum of these values turns out to be $89$ and the number of ways to flip is $1024$, but that is wrong. What is wrong with my solution? Thanks!

Best Answer

Your starting point has two flaws:

  • It forgets about Heads that could occur at the end of the string
  • It makes no difference between [Tails] and [Tails preceded by Heads] (in other words the equation $2x+y=10$ is wrong).

One way to get there without much trouble is this one:

  1. Fix the amount of Heads (could be anything between $0$ and $5$),
  2. Place them in a row, with one mandatory Tails in between each pair,
  3. Use the Stars and Bars formula to compute the number of ways to add the remaining Tails.
Related Question