<s>[INST] Recurrence relation for number sequence Let $a_n$ be the number of sequences of $n$ numbers, consisting of $0's, 1's$ and $2's$, such that a number $1$ on the $j$-th place isn't followed by a $1$ or $2$ on the $j+1$-th place for $1\leq j\leq n-1$.
I'm asked to prove that the correct recurrence relation for this sequence is given by $$a_n=2a_{n-1}+a_{n-2}, a_1=3,a_2=7$$

A shorter sequence can be extended in the following ways: let there be $x$ correct sequences with length $n$. Let's say $y$ sequences of length $n$ don't end with an $1$, that means you can extend those sequences with any of the three possibilities, giving $3y$ new sequences of length $n+1$. For the other $x-y$ sequences, ending in $1$, they can only be extended with a $0$, giving $x-y$ new sequences. The total number of new sequences now is $3y+x-y = 2y+x$. This seems going in the correct direction, I just don't see how they are linked to $a_{n-1}$ and $a_{n-2}$.
 [/INST] Got the recurrence, now solve it. You have:
$$
a_{n + 2} = 2 a_{n + 1} + a_n
$$
There is 1 zero-length sequence, and 3 one-length sequences; this checks $a_2 = 7$.
Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$. Then recognize:
\begin{align}
\sum_{n \ge 0} a_{n + 1} z^n &= \frac{A(z) - a_0}{z} \\
\sum_{n \ge 0} a_{n + 2} z^n &= \frac{A(z) - a_0 - a_1 z}{z^2}
\end{align}
to get:
$$
\frac{A(z) - 1 - 3 z}{z^2} = 2 \frac{A(z) - 1}{z} + A(z)
$$
Solving:
$$
A(z) = \frac{1 + z}{1 - 2 z - z^2}
$$
Calling $r_1 = 1 + \sqrt{2}$, $r_2 = 1 - \sqrt{2}$, we can write:
$$
A(z) = \frac{r_1 + 1}{2^{3/2} (1 - r_1 z)} - \frac{r_2 + 1}{2^{3/2} (1 - r_2 z)}
$$
This is just two geometric series:
$$
a_n = \frac{r_1 + 1}{2^{3/2}} \cdot r_1^n - \frac{r_2 + 1}{2^{3/2}} \cdot r_2^n
$$
</s>