I am fairly confused with this problem and I am not looking for an answer, but an explanation as to why my initial set up of this problem is incorrect. I believe that once I Understand this bit of the question then I will be able to solve the rest my self, so please do not answer this question for me. I only want a partial explanation to my set up.
Question:
Consider ternary strings where $0$, $1$, $2$ are the only symbols used. Let $a_n$ count the number of ternary strings of length $n$ where there are no consecutive $1$'s and no consecutive $2$'s. Find and solve a recurrence relation for $a_n$.
Basically I set it up as this
$$
a_n = a_{n-1} + a_{n-2}
$$
however, the hint given for the set up is
$$
a_n = 2a_{n-1} + a_{n-2}
$$
Can someone explain to me why we are multiplying $a_{n-1}$ by $2$? Note that $a_{n-1}$ represents strings that end in $0$ and hence the remaining sequences is $n-1$. If it ends in $1$ or $2$ then there are $n-2$ left sequences that have no consecutive $1$ and $2$.
Best Answer
A way to find this recurrence equation is to "count" the number of strings beginning (or ending!) with $0, 1, \text{ and } 2$ respectively.
Let $\alpha_n$ be the number of strings of length $n$ that begin with $0$, $\beta_n$ the number of strings that begin with $1$ and $\gamma_n$ the number of strings that begin with $2$. Then, we have the following relations :
\begin{equation} a_n = \alpha_{n} + \beta_{n} + \gamma_{n}, \end{equation} which simply states that the number of strings of length $n$ is the sum total of the number of strings of length $n$ beginning with $0, 1 \text { and } 2$, and
\begin{align} \alpha_n &= \alpha_{n-1} + \beta_{n-1} &+ \gamma_{n-1}\\ \beta_n &= \alpha_{n-1} &+ \gamma_{n-1}\\ \gamma_n &= \alpha_{n-1} + \beta_{n-1}& \end{align}
since you can tack a 0 before any string but a 1 (or a 2) only before strings beginning with another number. (By the way here, $\beta_n = \gamma_n$ but that's not even useful.)
Adding these three equations, and noticing that $\alpha_n = a_{n-1}$ (the number of strings of length $n$ beginning with $0$ is equal to the number of strings of length $n-1$) easily yields
\begin{equation} a_n = 2 a_{n-1} + a_{n-2} \end{equation} as stated.
I should say that in order to find these equations, I experimented a little by enumerating the strings of length 1, 2, 3, and that's how I saw the pattern emerge. That's a fairly standard way of investigating recurrence problems, as explained for instance in "Concrete Mathematics" by Graham, Knuth, and Patashnik.