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}$.
 A: Let $S_n$ be the set of sequences constructed according to the rules. Then for $n > 2$ find a bijection
$$r_n \colon S_n \to S_{n-1}\times \{1,2\} \cup S_{n-2}$$
to prove the recurrence. To find the bijection, think of how a shorter sequence may be extended. Find the right end at which to extend the sequences.

 Each sequence in $S_n$ starts with $0,1$, or $2$. If it starts with $0$ or $2$, the tail of the sequence is an arbitrary element of $S_{n-1}$. If it starts with a $1$, then the second symbol must be a $0$, but the remaining part of the sequence can be an arbitrary element of $S_{n-2}$. Thus $$r_n (s_1,s_2,\dotsc,s_n) \mapsto \begin{cases} ((s_2,\dotsc,s_n),s_1/2+1) &, s_1 \neq 1\\ (s_3,\dotsc,s_n) &, s_1 = 0 \end{cases}$$ is such a bijection, hence $a_n = 2a_{n-1} + a_{n-2}$ for $n > 2$.

A: 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
$$
