Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are $2^n$ equally likely outcomes when flipping a fair coing $n$ times. The probability in question can be written: $$p_{2,n}=\frac{R(2,n)}{2^n}$$ Where the numerator, $R(2,n)$ counts the number of sequences of $n$ flips of a fair coin where there is at least one run of heads of length at least $2$.

My approach: Count the number of sequences without a run of length at least $2$ and subtract from $2^n$. I have split the counting job into two cases:

$n$ odd: Start with the case where we have alternating heads and tails throughout which we write as: $$HTHTHT...HTH$$ or $$THTHTH...THT$$ We have the two cases here where the sequence starts (and ends) with $H$ or $T$.

For each of these starting positions, each $H$ can remain an $H$ or "morph" into a $T$ and so we have $2^{\lfloor{\frac{n+1}{2}}\rfloor}$ and $2^{\lfloor{\frac{n}{2}}\rfloor}$ for the first and second cases above respectively. Also, we count the case where all flips are $T$ twice here so finally we must add $1$. And this is it so for $n$ odd we get: $$R(2,n) = 2^n - 2^{\lfloor{\frac{n+1}{2}}\rfloor} - 2^{\lfloor{\frac{n}{2}}\rfloor}+1$$

$n$ even: Again we have two cases: $$HTHTHT...HT$$ and $$THTHTH...TH$$ and by the same logic as above we have in each case, $2^{\frac{n}{2}}$ sequences without the run we are looking for. Again we count the case where all flips are $T$ twice again so we must subtract it out but we are missing the case where the first and last flip are $H$ and the rest are $T$ so in total we adjust our count by $0$ giving for $n$ even: $$R(2,n) = 2^n - 2^{\frac{n}{2}+1}$$.

My question: I have doubts about this derivation. Even if it is correct I would be interested in a formula for all $n$ since I think splitting it into cases depending on parity is "messy". Anyone know of any corrections/improvements or other proofs/formulas? Thanks.

share|improve this question
With this reasoning, you won't count all sequences. For example: THHT... –  barto Sep 11 '13 at 18:31

1 Answer 1

up vote 1 down vote accepted

Hint: Your basic strategy is right. We count the number of strings of length $n$ with no two consecutive heads, more briefly bad strings. Denote the number of bad strings of length $n$ by $b_n$.

A bad string of length $n+1$ ends with either a $T$ or an $H$. If it ends in $T$, it has shape $\sigma T$, where $\sigma$ is any bad string of length $n$. If it ends with an $H$, it has shape $\sigma TH$, where $\sigma$ is any bad string of length $n-1$. That gives the Fibonacci recurrence $$b_{n+1}=b_n+b_{n-1}.$$

Calculate $b_1$ and $b_2$. Look up the closed-form "Binet" formula for Fibonacci numbers. Be careful about the indexing.

share|improve this answer
Now that is the type of approach I was looking for! Is it then true that, since $b_2$ = $3$ and $b_3$ = $5$ we have $b_n$ = $F_{n+3}$ since we are starting at the 5th and 6th terms of the Fibonacci sequence? (Assuming $F_n = $${0,1,1,2,3,5,8,...}$. Thus: $R(2,n) = 2^n - F_{n+3}$? –  Patrick Sep 11 '13 at 18:55
It is right, except that the indexing of the Fibonacci is not done in the same way by everyone. So when you look up the Binet Formula, you do have to check, by testing at a very small $n$, or maybe two, whether the indexing is the "right" one. –  André Nicolas Sep 11 '13 at 19:02
Do you happen to know of a good source of problems that are solved in this way (i.e. linear recurrence relations). I'm interested in learning more about this technique. –  Patrick Sep 11 '13 at 19:34
I don't have a source, but every beginning combinatorics course has such problems. If you ask that as a question on MSE, I expect you will get useful comments/answers. –  André Nicolas Sep 11 '13 at 19:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.