Q-->Find a recursive solution for $S_n$ the number of sequences of length $n$, composed of the letters $a$, $b$ or $c$ in which no sequence contains consecutive b's. Give detailed explanations.
what i did so far:
\begin{alignat}{2}
S1&= (a),(b),(c) &&{}=3\\
S2&= (a,a), (c,c), (a,b), (c,a), (b,a), (a,c), (b,c), (c,b) &&{}=8
\end{alignat}
this is what i tried so far..not even sure if im on the correct path..help
We can seperate the sequences of length $n$ of that type into two kinds, those that end in $b$ and those that don't.
How many don't end in $b$? We just need for the first $n-1$ digits not to contain consecutive $b$'s and then there are two options for the final digit. So there are $2S_{n-1}$ of those.
How many do end in $b$? well, the second to last letter must not be $b$, so there are two options for that letter. And the remaining part must not contain two consecutive letters $b$, so there are $2S_{n-2}$ of those.
Thus we get the recursion $S_n=2(S_{n-1}+S_{n-2})$