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!
 A: This problem is best approached through a recurrence relation.
Let $a_n$ denote the number of permissible sequences of length $n$.
No sequence of length $1$ can have two consecutive $2$'s.  Since there are three ways the first position can be filled, $a_1 = 3$.
The only sequence of length $2$ that has two consecutive $2$'s is $22$.  Since each of the two positions can be filled in two ways, $a_2 = 3 \cdot 3 - 1 = 8$.  
Notice that any permissible sequence of length $n$ can be extended to a sequence of length $n + 1$ by appending a $0$ or a $1$ to the end of the permissible sequence of length $n$.
We can only have a permissible sequence of length $n + 1$ that ends in a $2$ if the $n$th digit is a $0$ or a $1$.  Hence, any permissible sequence of length $n - 1$ can be extended to a permissible sequence of length $n + 1$ by appending $02$ or $12$ to the end of the permissible sequence of length $n - 1$.  
Hence, we have the recurrence relation
\begin{align*}
a_1 & = 3\\
a_2 & = 8\\
a_{n + 1} & = 2a_n + 2a_{n - 1}, n \geq 2
\end{align*}
If I am interpreting your attempt correctly, you are trying to eliminate those sequences with two or more consecutive $2$'s.  However, you have only excluded those sequences in which all the $2$'s are consecutive.  They can also appear in disjoint pairs.  For instance, both the sequences $12220$ and $22122$ have two pairs of consecutive $2$'s.  The consecutive pairs overlap in $12220$ and are disjoint in $22122$.  Trying to count pairs of consecutive $2$'s becomes trickier as $n$ increases, which is why I approached the problem through a recurrence relation. 
A: Forgive the second answer, but I can't comment on the previous answer (not yet enough reputation). The recurrence in N.F. Taussig's answer is correct (and very concisely explained!). I would add you can get a closed form, since this is a linear recurrence. In this case it's very nice (see http://mathworld.wolfram.com/LinearRecurrenceEquation.html).
Any permissible sequence of length $n$ can be extended to a permissible sequence of length $n+1$ by appending a $0$ or a $1$ (there's the $2a_n$). A permissible sequence of length $n+1$ that ends in a $2$ must be obtained from a permissible sequence of length $n-1$ by appending either $02$ or $12$ (not $01$ or $02$, and there's the $2a_{n-1}$).
Either way, the recurrence relation is certainly $$a_{n+1}=2a_n+2a_{n-1},n\ge 2.$$
A: 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).

