-2

If you toss a coin $n$ times, there are $2^n$ posible sequences of heads and tails. Let $E_n$ be the set of sequences which do NOT contain two consecutive heads and $e_n$, the number of sequences in $E_n$.

Thus $E_3$ $=$ $\{$ $TTT$, $TTH$, $THT$, $HTT$, $HTH$ $\}$ and $e_3$ $=$ $5$.

How many elements of $E_n$ have $H$ as the first toss and $T$ as the second?

N. F. Taussig
  • 76,571
B.Pickett
  • 5
  • you are just looking at the strings of the form $HT-E_{n-2}$ so you need to compute $e_n$. Having $T$ has your second toss "resets" your condition – Spotty Mar 26 '17 at 19:10
  • This is not sufficiently different from presumably your last question: http://math.stackexchange.com/questions/2204139/how-many-sequences-of-n-tosses-of-a-coin-that-do-not-contain-two-consecutive-h?noredirect=1&lq=1 The exact same logic explained in that post applies to this post as well. – JMoravitz Mar 26 '17 at 19:12
  • 2
    In this site there are thousands of questions about combinatorics. Your question is certainly not the second one! Please edit your question so that the title is useful. – Mariano Suárez-Álvarez Mar 26 '17 at 19:24

1 Answers1

0

This links neatly to the Fibonacci sequence.

Obviously $e_1=2, e_2=3$. Then longer sequences can be generated by considering that to derive $e_n$, there will be $e_{n-1}$ sequences in $E_n$ starting with $T$ and $e_{n-2}$ sequences starting with $H$, because they have to then continue with a $T$. This gives $e_n = e_{n-1}+e_{n-2}$ (so $e_i$ starts $2,3,5,8,13,21$ etc.) and incidentally the answer to your question that $e_{n-2}$ elements of $E_n$ start with $HT$.

Joffan
  • 39,627