$a_n$ is the number of sequences with length $n$ over ${1,2,3}$

Question

$a_n$ is the number of sequences with length $n$ over ${1,2,3}$ such as there ain't no two number '1' next to each other.

Find a formula for $a_n$.

I thought about splitting it to one case where number in the last place was one, so the following must be 2 or 3 and a case where the three options are available. I'm having hard time putting it into formula and in general approaching those kind of questions.

I looked into other questions up here and still had hard time putting the concepts into this one.

Answer 1

Let's call a sequence of $1$'s, $2$'s, and $3$'s "valid" if it doesn't have two consecutive $1$'s. Every valid sequence of length-$n$ fits one of these cases:

A) [valid sequence of length $n-1$], $2$

B) [valid sequence of length $n-1$], $3$

C) [valid sequence of length $n-2$], $2$, $1$

D) [valid sequence of length $n-2$], $3$, $1$

By considering these cases, can you find the number of valid sequences of length-$n$ in terms of the number of valid sequences of lengths $n-1$ and $n-2$? i.e. find $a_n$ in terms of $a_{n-1}$ and $a_{n-2}$.

After doing that, you'll have a recursive formula for $a_n$. From there, you just need to come up with some initial values and solve the 2nd order linear recursion.