<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] 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$.
</s>