Let $C_n$ be the number of sequences with a length of n, which their elements belong to $\{0,1,2\}$, and they don't contain the following sequences: $11,21$. Find a recursion formula with starting conditions for $C_n$.
$Solution.$ Let $C_n$ be the number of valid sequences with a length of $n$.
We consider three possible cases:
- The first number of the sequence is zero: then we can take valid sequences with a length of $n-1$. Therefore we have $C_{n-1}$ options for this case.
- The first number of the sequence is one: we cannot have after 1 another 1, so we should apply the complement method. We take all valid sequences with a length of $n-1$ and remove all valid sequences with a length of $n-1$ starting with 1. Therefore, we get: $C_{n-1}-C_{n-2}$.
- The first number of the sequence is two: in this case, we should also apply the complement method. Similarly to case 2, we get: $C_{n-1}-C_{n-1}^{'1'}=C_{n-1}-(C_{n-2}-C_{n-3})=C_{n-1}-C_{n-2}+C_{n-3}$.
In total we get: $$C_{n-1}+C_{n-1}-C_{n-2}+C_{n-1}-C_{n-2}+C_{n-3}=3C_{n-1}-2C_{n-2}+C_{n-3}$$
Starting conditions, $$C_{0} =1,C_{1} =3,C_{2} =7$$
Now, by a simple test for this formula, we get that $C_3=16$ and it isn't true since $C_3=17$. The main purpose of this question is to know how to systematically solve such questions. I don't really know when to apply the complement method, and how to approach in general to solve combinatorial problems with a recursion formula. Thanks!
For $C_3$ we have the following 17 options: $$ \begin{array}{l} \ \ 1\ 0\ 0\ |1\ \\ 1\ 0\ 1\ |2\\ 1\ 0\ 2\ |3\\ 1\ 2\ 0\ |4\\ 1\ 2\ 2\ |5\\ 2\ 0\ 0\ |6\\ 2\ 0\ 1\ |7\\ 2\ 0\ 2\ |8\\ 2\ 2\ 0\ |9\\ \ \ 2\ 2\ 2\ |10\\ \ \ 0\ 0\ 0\ |11\\ \ \ 0\ 0\ 1\ |12\\ \ \ 0\ 0\ 2\ |13\\ \ \ 0\ 1\ 0\ |14\\ \ \ 0\ 1\ 2\ |15\\ \ \ 0\ 2\ 0\ |16\\ \ \ 0\ 2\ 2\ |17 \end{array}$$
Just after typing an answer completing your approach, I noticed that there is a way easier one. I will leave my original thoughts below because it may interest you how you could have proceeded with your approach.
It is much easier to think about the last digit than the first. If the last digit is a $0$ or a $2$, any sequence of length $n-1$ works before that, and if the last digit is a $1$, the rest of the sequence has to end in a $0$, which in turn means that the first $n-2$ digits have to form an arbitrary valid sequence. From there we immediately arrive at the recursive formula $C_n=2C_{n-1}+C_{n-2}$.
Now as promised the more complicated approach considering the first digit: Let $x_n^{(k)}$ denote the number of sequences of length $n$ that start with the digit $k$, obviously we have $C_n=x_n^{(0)}+x_n^{(1)}+x_n^{(2)}$. Let's find recursive formulas for the $x_n^{(k)}$. For $k=0$, we have $$x_n^{(0)}=x_{n-1}^{(0)}+x_{n-1}^{(1)}+x_{n-1}^{(2)}=C_{n-1}$$ since a $0$ can be added to every sequence of length $n-1$. For $k=1$ and $k=2$, the rest of the sequence may not start with a $1$, so we have $$x_n^{(1)}=x_n^{(2)}=x_{n-1}^{(0)}+x_{n-1}^{(2)}.$$ Now we put this together and calculate a formula for $C_n$: \begin{align*}C_n&=x_n^{(0)}+x_n^{(1)}+x_n^{(2)}=C_{n-1}+2\left(x_{n-1}^{(0)}+x_{n-1}^{(2)}\right)\\&=C_{n-1}+x_{n-2}^{(0)}+x_{n-2}^{(1)}+x_{n-2}^{(2)}+x_{n-1}^{(0)}+2x_{n-1}^{(2)}\\&=C_{n-1}+x_{n-1}^{(1)}+x_{n-2}^{(1)}+x_{n-1}^{(0)}+x_{n-1}^{(2)}+x_{n-1}^{(2)}\\&=2C_{n-1}+x_{n-2}^{(1)}+x_{n-2}^{(0)}+x_{n-2}^{(2)}\\&=2C_{n-1}+C_{n-2}.\end{align*}