Find an expression for Sn+1 in terms of Sn and Sn-1 which holds for all n >= 2

Question

Let Sn be the number of ternary strings of length n in which every 1 is followed immediately by a 2 (these strings cannot end with a 1). Find an expression for Sn+1 in terms of Sn and Sn-1 which holds for all n >= 2.

I have no idea how to solve this. I got the base cases S1 = 2 and S2 = 5 but I don't know how to proceed from here

Answer 1

Take a ternary string of length $n + 1$, and break it down into cases: does it end in $2$ or $0$?

If it ends in $0$, then removing that $0$ will result in a string counted by $S_n$. Moreover, any string counted by $S_n$ can have a $0$ tacked on the end and become a string counted by $S_{n+1}$ (since, of course, no such string can end in $1$).

If it ends in $2$, then we must be more careful. Removing the $2$ could expose a $1$ at the end of the string. So, we have two sub-cases. Either the string ends in $12$, or it ends in $02$ or $22$. If it ends in $12$, then removing these two terms will result in a string counted by $S_{n - 1}$, and conversely, any such string can have $12$ added to the end in order to make a string counted by $S_{n + 1}$.

Otherwise, if it ends in $02$ or $22$, then removing the last $2$ will produce a string counted by $S_n$ (and the converse holds too).

So, the first case, when the string ends in $0$, produces exactly $S_n$ strings.

The second case had two subcases: when the string ends in $12$, there are exactly $S_{n - 1}$ such strings. When the string ends in $02$ or $22$, there are exactly $S_n$ strings.

Putting it together, we get $$S_{n + 1} = 2S_n + S_{n - 1}.$$

Answer 2

Let's consider the stings of length $n+1$ that end in $2$. Of course, we can add $2$ to any admissible string of length $n$. However, it's also possible to add the string $12$ to an admissible string of length $n-1.$

Thus, there are $S_n+S_{n-1}$ admissible strings of length $n+1$ that end in $2$. Now you have to count the admissible strings of length $n+1$ that end in $0$.

Answer 3

Suppose we have a valid string of length $n+1$. What is the first element? If it's $0$ or $2$, the string we get by cutting off that first element is a valid string of length $n$ - and conversely, adding that $0$ or $2$ to the front of any valid string of length $n$ gets us a valid string of length $n+1$. That's $2S_n$ strings starting with $0$ or $2$.
If the first element is $1$ instead, then we know that the second element is $2$. Cut off both of those, and what's left is a valid string of length $n-1$ - and conversely, every valid string of length $n-1$ can have $12$ added to the front to get us a valid string of length $n+1$. That's $S_{n-1}$ strings of starting with $1$.

Combine the two, and we get $S_{n+1}=2S_n+S_{n-1}$. One term for the strings that start with $0$ or $2$, another term for those that start with $1$.