Coin Recurrence Game
Solution 1:
For $n$ coins you go through the sequence with $n-1$ coins and a final head. That provides $a_{n-1}$ arrangements with the last coin $H$. Then you flip the final coin to tails and all the preceding coins to heads. Neither of the last two coins can change any more, so you go through $a_{n-2}$ arrangements with the two last coins $HT$
Solution 2:
One way to do it is to prove that your algorithm iterates through all the sequences that do not contain consecutive $T$'s in inverse lexicographic order (where $T$ is considered larger than $H$).