Recurrence relation for number sequence

Question

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}$.

Answer 1

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$.

Answer 2

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