Coin tossing problem where three tails come in a row

Question

The problem is if I want to toss a coin n times, what is the number of ways possible when three tails comes in a row? For example if I toss a coin for 4 times, the number of ways where 3 tails come in row is 3 i.e. TTTT, TTTH, HTTT. I need a generalized explanation for this.

Answer 1

This is a classical problem.

We instead count the complement: The number of ways to have it so that no three tails are in a row. Later we subtract from $2^n$, the total number of sequences. This we can do by recursion. Let $x_n$ be the number of sequences of $n$ flips without TTT. For $n=0,1,2$, our answer is $1,2,4$, respectively.

If $n\geq 3$, note that the sequence ends with one of H, HT, HTT, since the last H must be one of the last 3 flips, or else the last 3 flips are all tails, which is not allowed.

Furthermore, appending H, HT, or HTT to a valid sequence produces another valid sequence. So, if it ends with H, there are $x_{n-1}$ ways to pick the first $n-1$ flips; if it ends with HT, there are $x_{n-2}$ possibilities for the first $n-2$ flips; and if it ends with HTT, we have $x_{n-3}$ choices.

Hence, $$\boxed{x_n = x_{n-1}+x_{n-2}+x_{n-3}}.$$ You can now use this to generate $x_n$ for any value of $n$, and take $2^n-x_n$ to compute the answer to your question.

Unfortunately, closed forms of this are weird, since in order to solve the recurrence we need the roots of the characteristic polynomial, which are quite disgusting in this case.