Coin Recurrence Game

Question

Hi I'm struggling with the following homework problem:

Let's play a game. We start with $n$ coins side by side in a row which all happen to be heads. We apply the following operation to the row until we can't any more. As we traverse through the row from left to right, we take the first heads that is not followed by a tail, flip it, and restore all coins on its left to heads. How many different arrangements appear at one point in the process? For example, the arrangements for $n=3$ would be: HHH, THH, HTH, HHT, THT in that order.

So I listed out a couple of small cases for n, and quickly found the recurrence $a_n = a_{n-1} + a_{n-2}$ where $a_n$ is the number of arrangements that appear during the process. However, I am at a loss on how to rigorously prove this. Any advice would be helpful, thanks!

Answer 1

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$).

Answer 2

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$