# Counting the sequences of coin flips that end HH after $n$ flips (a more efficient method?)

I figured out that for any given $n$ the number of sequences of heads and tails that satisfy the condition that HH wasn't flipped consecutively until flips $n-1$ and $n$ is equal to the $(n-1)$th Fibonacci number. I found this by making a tree whose root was T on the $(n-2)$ flip and then I branched to each possible way to fill the $(n-3)$ slot and from those branches I branched to the possibilities for the $(n-4)$ slot, etc. It was neat to see the Fibonacci sequence pop up here, but I want to know how to find the result efficiently using a method from combinatorics.

Count the sequences that have no $HH$ at all in them. Such sequences of length $n+2$ are either of the form $\alpha T$ where $\alpha$ is an arbitrary such sequence of length $n+1$ or of the form $\beta TH$ where $\beta$ is an arbitrary such sequence of length $n$. Finally the sequences ending in a first occurance of $HH$ are (if $n\ge 3$) of the form $\gamma THH$ where $\gamma$ is of the form just described.