Recurrence of $\{0,1,2\}^n$ tuples that don't contain $2$ followed immediately by $0$

Question

I'm doing part (a) and need some hints with it.

My approach is to divide members of $\{t_n\}$ into 2 sets:

$\bullet$ n-tuples start with $0$, i.e. $(0,\_ \ ,\_ \ ,\_ \ ,\_ \ ,\_ \ ,...)$: there are $t_{n-1}$ of those (i.e. we fill in the blanks with members of $\{t_{n-1}\}$).

$\bullet$ n-tuples with $0$ in position $p$, for $p = 2,3,...,n-1$, $\ $ i.e. $(...,\_ \ ,\_ \ , 0,\_ \ ,\_ \ ,\_ \ ,...)$: we want to fill the blanks with $\{t_{n-1}\}$, except those that have $2$ at position $(p-1)$, $\ $and there are $t_{n-2}$ of those. Since there are $(n-2)$ possible values for $p$, the count would be $(n-2)(t_{n-1} - t_{n-2})$.

I get stuck when it's time to sum up the above. I think they overlap, especially those in the second bullet point, but can't decide where.

==============================================

Edit: I've now realized that my division of cases is wrong, thanks to the answers by Henning Makholm and Hagen von Eitzen (and also to the comment by another user, which for some reason was gone). The first of the sets is good, but the second one doesn't complement it. I'm thinking more about this problem and will edit my question again if needed.

Answer 1

The first of the sets is a good start, but why isn't your other set simply the valid $n$-tuples that start with $1$ or $2$?

To extend a tuple from the first class, you can stick either a $0$ or an $1$ in front of it.

To extend a tuple from the second class, you can stick $0$, $1$, or $2$ in front of it.

This gives you a coupled first-order recurrence between the number of tuples in each of the sets as $n$ increases.

Answer 2

A better idea may be to let $a_n, b_n, c_n$ count the strings without $2$ followed by $0$ that start with $0,1,2$, respectively. Then note that $$\begin{align} t_n&=a_n+b_n+c_n\\ a_n&=t_{n-1}\\ b_n&=t_{n-1}\\ c_n&=b_{n-1}+c_{n-1}\end{align}$$ and simplify.

Answer 3

As you noted in a comment, the recurrence is $t_n=3t_{n-1}-t_{n-2}$, and there is a simple proof of this. To choose a string of length $n$, you

1. Choose the last character [$3$ choices].
2. Choose the first $n-1$ characters so no instances of "$20$" appear [$t_{n-1}$ choices].
3. Remove any "bad" strings produced by the first two steps which end in "$20$" [there are $t_{n-2}$ such strings].

You can then solve that recurrence using the usual method, and then realize that it matches Binet's formula for $F_{2n+2}$.

---

Here is a direct proof that the number of strings is given by $F_{2n+2}$. Note $F_{2n+2}$ is the number of ways to tile a strip of unit squares of length $2n+1$ with squares and dominoes. Divide this strip into $n$ consecutive sections of length two, followed by a final square. There are three choices for each section:

(0) The right square is covered by the right half of a domino.
(1) The right square is covered by a square tile.
(2) The right square is covered by the left half of a domino (which juts into the next section).

It turns out these choices completely describe the tiling. For example, here is the tiling corresponding to the string $00122102$, where X is a square and $<>$ is the two parts of a domino, while the |s are the section dividiers.

 0  0  1  1  2  2  1  0  2
<>|<>|XX|XX|X<|><|>X|<>|X<|>

Note that case (2) cannot be followed by case (0), because the two dominos would necessarily overlap. Therefore, the tiling is described by a string of $n$ $0$s, $1$s and $2$s following the same restrictions as your problem.