<s>[INST] Number of strings of length n formed by $\{0,1,2\}$ such that $1$ and $2$ do not occur successively. What is the number of ways of forming a string of length $n$ from the set $\{0,1,2\}$ such that $1$ and $2$ do not occur successively.
 [/INST] There is an interesting related problem that has a solution using inclusion-exclusion. This is the restriction of the inadmissible words to words where $1$ and $2$ occur in order. This requires that we count the number of $n$-strings having $k$ instances of $1$ followed by $2$ ocurring successively with $1\le k \le \lfloor n/2 \rfloor$. This count can be done by considering the length of the possible gaps between these pairs, which are given by the generating function
$$\left(\frac{1}{1-z}\right)^{k+1}.$$
The total of these gaps must equal $n-2k$, giving
$$[z^{n-2k}] \left(\frac{1}{1-z}\right)^{k+1}
= {n-2k+k\choose n-2k} = {n-2k+k\choose k} = {n-k\choose k}.$$
Therefore by inclusion-exclusion the number of strings of length $n$ containing at least one occurrence of $1$ and $2$ in order is given by
$$\sum_{k=1}^{\lfloor n/2 \rfloor} (-1)^{k+1} {n-k\choose k} 3^{n-2k}$$
and the count where $1$ and $2$ do not occur successively is
$$3^n + \sum_{k=1}^{\lfloor n/2 \rfloor} (-1)^k {n-k\choose k} 3^{n-2k}
= \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k {n-k\choose k} 3^{n-2k}.$$
If we compute this for small values we obtain the sequence
$$1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040,\ldots$$
which is A001906 from the OEIS.
Call this sequence $\{a_n\}$. The ordinary generating function of this sequence is given by
$$f(z) =
\sum_{n\ge 0} \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k {n-k\choose k} 3^{n-2k} z^n.$$
Rearranging the sum we find that
$$f(z) = \sum_{k\ge 0} \sum_{\lfloor n/2 \rfloor\ge k} (-1)^k {n-k\choose k} 3^{n-2k} z^n =  \sum_{k\ge 0}  (-1)^k \times 3^{-2k}
\sum_{\lfloor n/2 \rfloor\ge k}{n-k\choose k} 3^n z^n .$$
The inner sum can be manipulated as follows:
$$\sum_{n\ge 2k} {n-k\choose k} 3^n z^n 
= \sum_{n\ge 0} {n+2k-k\choose k} 3^{n+2k} z^{n+2k}
= 3^{2k} z^{2k} \sum_{n\ge 0} {n+k\choose k} 3^n z^n\\
= 3^{2k} z^{2k} \sum_{n\ge 0} {n+k\choose n} 3^n z^n
=  3^{2k} z^{2k} \left(\frac{1}{1-3z}\right)^{k+1}.$$
This finally gives for the generating function that
$$f(z) = \sum_{k\ge 0}  (-1)^k z^{2k}  \left(\frac{1}{1-3z}\right)^{k+1}
= \frac{1}{1-3z} \sum_{k\ge 0}  (-1)^k z^{2k} \left(\frac{1}{1-3z}\right)^k
= \frac{1}{1-3z} \frac{1}{1+z^2/(1-3z)} = \frac{1}{1-3z+z^2}.$$
The inverses of the poles of $f(z)$ are given by
$$\rho_{0,1} = \frac{3\pm\sqrt{5}}{2}$$
leading to the closed form
$$a_n = \frac{1}{\sqrt{5}}
\left(
\left(\frac{3+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{5}}{2}\right)^{n+1}
\right).$$
</s>