<s>[INST] How many words of length $n$ can we make from $0, 1, 2$ if $2$'s cannot be consecutive? How many words we can make from $0,1,2$? The restriction is we can't put the digit $2$ after the digit $2$.
My solution:
I tried to solve it with Inclusion-Exclusion Principle.  Count the number of the words without restriction and then I decreased the options that I don't want. The number of ways to make words without restriction $3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot \ldots \cdot 3$, so this is $3^n$.  And then the number that I don't want to count is: 
$$\binom {n-1}{2} - \binom {n-2}{3} + \cdots + (-1)^n \cdot \frac{ (n-(n+1)}{(i+1)!}$$
so my solution is $$3^n - \sum_{i=1}^n-1 \frac{(-1)^n \cdot (n-i)}{(i+1)!}$$
This is not the answer. Can someone help me? What did I do wrong? 
Does the problem have any solution with a recurrence relation??
Thanks for your help!
 [/INST] This answer is based upon the Goulden-Jackson Cluster Method which is a convenient method to derive a generating function for problems of this kind.

We consider words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1,2\}$$ and the set $\mathcal{B}=\{22\}$ of bad words, which are not allowed to be part of the words we are looking for.
We derive a function $F(x)$ with the coefficient of $x^n$ being  the number of wanted words of length $n$.
  According to the paper (p.7) the generating function $F(x)$  is
  \begin{align*}
F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})}
\end{align*}
  with $d=|\mathcal{V}|=3$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with
  \begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[22])
\end{align*}

We calculate according to the paper
\begin{align*}
\text{weight}(\mathcal{C}[22])&=-x^2-\text{weight}(\mathcal{C}[22])x
\end{align*}
and get
\begin{align*}
\text{weight}(\mathcal{C}[22])=-\frac{x^2}{1+x}
\end{align*}
It follows:

A generating function $F(x)$ for the number of words built from $\{0,1,2\}$ which do not contain the subword $22$ is
  \begin{align*}
F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\
&=\left(1-3x+\frac{x^2}{1+x}\right)^{-1}\\
&=\frac{1+x}{1-2x-2x^2}\\
&=1+3x+8x^2+\color{blue}{22}x^\color{blue}{3}+60x^4+164x^5+448x^6\\
&\qquad+1224x^7+3344x^8+9136x^9+\cdots\tag{1}
\end{align*}

We see e.g. the term $22x^3$ indicates there are $\color{blue}{22}$ different words of length $\color{blue}{\text{three}}$ built from $\{0,1,2\}$ which do not contain $22$. Out of the $3^3=27$ different words of length three built from $\{0,1,2\}$ there are precisely five words
\begin{align*}
022,122,222,221,220
\end{align*}
which are to exclude, resulting in a total of $27-5=22$ words.
Using partial fraction decomposition we can derive a representation of $F(x)$ as geometric series expansion. From this representation we can easily obtain the coeffcients of $x^n$ which are the number of wanted words, i.e. the words which do not contain $22$.
We obtain
\begin{align*}
F(x)&=\frac{1+x}{1-2x-2x^2}\\
&=\frac{2+\sqrt{3}}{2\sqrt{3}}\cdot\frac{1}{1-(1+\sqrt{3}x)}-\frac{2-\sqrt{3}}{2\sqrt{3}}\cdot\frac{1}{1-(1-\sqrt{3}x)}\\
&=\frac{2+\sqrt{3}}{2\sqrt{3}}\sum_{n=0}^\infty(1+\sqrt{3})^nx^n-\frac{2-\sqrt{3}}{2\sqrt{3}}\sum_{n=0}^\infty(1-\sqrt{3})^nx^n\\
\end{align*}
and conclude:

The number of words of length $n$ built from $\{0,1,2\}$ which do not contain $22$ is
  \begin{align*}
\frac{2+\sqrt{3}}{2\sqrt{3}}(1+\sqrt{3})^n-\frac{2-\sqrt{3}}{2\sqrt{3}}(1-\sqrt{3})^n\qquad\qquad n\geq 0
\end{align*}
  which is a sequence starting with
  \begin{align*}
1,3,8,22,60,164,448,1224,3344,9136,\ldots
\end{align*}
  in accordance with (1).

</s>