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.
 A: Let $A_n,B_n,C_n$ be the number of such strings of length $n$ ending in $0$, $1$ and $2$, respectively. We are looking for $f(n)=A_n+B_n+C_n$.
Clearly $A_1=B_1=C_1=1$. We have the recursions $B_{n+1}=A_n+C_n$, $C_{n+1}=A_n+B_n$ and $A_{n+1}=A_n+B_n+C_n$.
By symmetry $B_n=C_n$ so that this simplifies to 
$$ \left(\begin{matrix}A_{n+1}\\B_{n+1}\end{matrix}\right)=\left(\begin{matrix}1&2\\1&1\end{matrix}\right)\left(\begin{matrix}A_{n}\\B_{n}\end{matrix}\right).$$
The matrix has eigenvalues $1\pm\sqrt 2$ so that the expression for $A_n$, $B_n$ and in fact also for the quantity $f(n)=A_n+2B_n$ needed in the end has the form
$$ f(n) = \alpha\left({1+\sqrt 2}\right)^n+\beta\left(1-\sqrt 2\right)^n.$$
The numbers $\alpha,\beta$ are obtained from $\alpha+\beta=f(0)=1$ and $(\alpha+\beta)+\sqrt2(\alpha-\beta)=f(1)=3$ as $\alpha=\frac{1+\sqrt 2}2$ and $\beta=\frac{1-\sqrt 2}2$, so that ultimately
$$ f(n) = \frac12\left(\left(1+\sqrt 2\right)^{n+1}+\left(1-\sqrt 2\right)^{n+1}\right).$$
A: I will solve it using recurrence relations. The trick is in formulating the recurrence relations. 
A string is called good if 1,2 do not occur successively. Let $a(n),b(n),c(n)$ be the number of good strings of length $n$ that end in $0,1,2$ respectively.For every good string of length $n$ that ends in $1$ or $2$ adding $0$ to it will make a good string of length $n+1$ that ends in $0$. It follows that:
$$a(n+1)=a(n)+b(n)+c(n)$$
Similarly (Here watch out that $1,2$ can't be consecutive):
$$b(n+1)=a(n)+b(n)$$
$$c(n+1)=a(n)+c(n)$$
The number that you are interested in is $a(n)+b(n)+c(n)$
A: Let's use generating functions (Wilf's "generationfunctinology explains the technique)to solve this one. Call $a_n$, $b_n$, $c_n$ the number of strings of length $n$ ending in 0, 1, 2 respectively. By considering the ways of getting strings of length $n + 1$ by appending a digit to sequences of length $n$, this leads to the recurrences (remember to take care not to get adyacent 1, 2):
$$
a_{n + 1} = a_n + b_n + c_n \\
b_{n + 1} = a_n + b_n \\
c_{n + 1} = a_n + c_n
$$
Also, $a_0 = b_0 = c_0 = 1$. We are interested in $f(n) = a_n + b_n + c_n = a_{n + 1}$. Define ordinary generating functions:
$$
A(z) = \sum_{n \ge 0} a_n z^n \\
B(z) = \sum_{n \ge 0} b_n z^n \\
C(z) = \sum_{n \ge 0} c_n z^n
$$
By the properties of ordinary generating functions:
$$
\frac{A(z) - a_0}{z} = A(z) + B(z) + C(z) \\
\frac{B(z) - b_0}{z} = A(z) + B(z) \\
\frac{C(z) - c_0}{z} = A(z) + C(z)
$$
Your tame computer algebra package solves this system of equations:
$$
A(z) = \frac{1 + z}{1 - 2 z - z^2} \\
B(z) = C(z) = \frac{1}{1 - 2 z - z^2}
$$
We are interested in $a_{n + 1}$:
$$
A(z) = \frac{1}{2 (1 + \sqrt{2})} \cdot \frac{1}{1 - (1 + \sqrt{2})^{-1} z} + \frac{1}{2 (1 - \sqrt{2})} \cdot \frac{1}{1 - (1 - \sqrt{2})^{-1} z}
$$
This gives:
$$
a_n = \frac{(1 + \sqrt{2})^{n - 1}}{2} + \frac{(1 - \sqrt{2})^{n - 1}}{2}
$$
The final answer is that there are:
$$
f(n) = a_{n + 1} = \frac{(1 + \sqrt{2})^n}{2} + \frac{(1 - \sqrt{2})^n}{2}
$$ strings in total of length $n$.
A: 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).$$
