Get 3 consecutive tails in coin flipping?

Question

I Have been trying for so Many days to find the solution of this problem

"The number of ways we can get atleast 3 consecutive tails if we toss the coin 'n' number of times?"

Can anyone help me here?

Answer 1

Count the number of ways to not get 3 consecutive tails, denote this number $a_n$. For $n\ge 3$, such a way will have a heads among the last three rounds, i.e., will end in either $H$ or $HT$ or $HTT$. Hence a way of length $n$ is either a way of length $n-1$ followed by $H$, a way of length $n-2$ followed by $HT$, or a way of length $n-3$ followed by $HTT$. Deduce that $$a_n=a_{n-1}+a_{n-2}+a_{n-3}$$ and use this recursion to express $a_n$. Subtract the result from $2^n$ to answer the original question.