Number of series of length n using 0,1,2 s.t between every two appearances of the digit 2, the digit 0 appears?

Question

I would appreciate your help. Below, I describe the question and my attempt to solve it.
Thanks in advance.

Question

Consider $A_n$ the set of $(a_1,a_2,\dots ,a_n)$ s.t:
1. $\forall i\in [n]:a_i \in {0,1,2}$
2.$\forall i<j$ :$a_i = a_j = 2\implies \exists i<k<j:x_k =0 $

Let $f(n)$ denotes the number of such $(a_1,a_2,\dots ,a_n)$.Find a recursive formula for $f(n)$.

My attempt

Lets define $g(n)$ as the number of $(a_1,a_2,\dots ,a_n)\in A_n$ s.t $(a_1,a_2,\dots ,a_n,2)\in A_{n+1}$.

Initial conditions of recursion:$f(0) = 1, f(1)=3, f(2) =8$.

Let $(a_1,a_2,\dots ,a_n)\in A_n$:

1. If $a_n =0 $:

   Then $(a_1,a_2,\dots,a_{n-1} ,a_n)=(a_1,a_2,\dots ,a_{n-1},0)$. There are $f(n-1)$ options for $(a_1,a_2,\dots ,a_{n-1})$.

2. If $a_n =1 $:

   Then $(a_1,a_2,\dots,a_{n-1} ,a_n)=(a_1,a_2,\dots ,a_{n-1},1)$. There are $f(n-1)$ options for $(a_1,a_2,\dots ,a_{n-1})$.

3. If $a_n =2 $:

   Then $(a_1,a_2,\dots,a_{n-1} ,a_n)=(a_1,a_2,\dots ,a_{n-1},2)$. There are $g(n-1)$ options for $(a_1,a_2,\dots ,a_{n-1})$.

I'm not sure how to continue my proof. I tried to calculate $g(n)$ (not even sure why).
I get $g(n) = f(n)-g(n-1)-g(n-2)$ (I don't know if I calculated $g(n)$ correctly. I asked students in my class and they got a different answer: $g(n) = f(n-1)+g(n-1)$).

Even if I calculated it correctly, I don't know how to continue from here. I would appreciate your help if you can explain me how to deal with two (or more) different recursive formulas.

Answer 1

For a simple combinatorial proof:

We note that removing the last character of a good string yields a good string. Conversely, however, we have to be careful. You can always append a $0$ or a $1$ but you can't always append a $2$. Let's keep track of that.

As in the post, let $f(n)$ be the number of good strings of length $n$. We divide these into two types. $f_1(n)$ denotes the number of good strings of length $n$ which can take any of the three letters as a suffix, $f_2(n)$ denotes those which can only take $0,1$. The strings of type $2$ are those that end in a word of the form $21^k$ for $k\in \{0,1,2, \cdots\}$, though we will not use this. Of course $f(n)=f_1(n)+f_2(n)$.

We can easily get a double recursion for the $f_i$. Indeed:

$$f_1(n)=2f_1(n-1)+f_2(n-1)\quad \&\quad f_2(n)=f_1(n-1)+f_2(n-1)=f(n-1)$$

Adding these we get $$f(n)=f_1(n)+f_2(n)=3f_1(n-1)+2f_2(n-1)=\cdots $$ $$\cdots =3f(n-1)-f_2(n-1)=3f(n-1)-f(n-2)$$ as desired.

Worth remarking that these are all Fibonacci numbers. The $f(n)$ (and therefore the $f_2(n)$) are the even indexed Fibonacci numbers and the $f_1(n)$ are the odd indexed Fibonacci numbers.

Answer 2

When you observe the 2 subsequences separately, the one with $1$'s and the other with $0$'s and $2$'s, then we get this: If we fix the lengths of these 2 subsequences, then there is only one possible configuration for the first one. Let's say the other was of length $k$. Your condition translates to that that there can't be two $2$'s next to each other in the second subsequence. You can prove by induction (i.e. recusrion, which you are already doing so I suppose you are familiar with it), that there are $F_{k+2}$ different configurations for the second subsequence. $F_k$ is $k$-th Fibonacci number, $F_3=2$. Now you can derive the next formula using the fact that $k$ could be anything from $0$ to $n$ and counting different ways a subsequence of length $k$ can be chosen from a sequence of length $n$ (the binomial coefficient): $$f(n)=\sum_{k=0}^n\binom{n}{k}F_{k+2},$$ where $f(n)$ is what you want to count for the length $n$. Use the explicit formula for the Fibonacci numbers and then use the binomial formula to get the final result. You will then get an explicit formula for $f(n)$ similar to that of Fibonacci numbers. You can translate it back into a recursion by constructing a polynomial whose zeros are the constants being raised to the power. They will be only 1 added to those of Fibonacci numbers (which is dictated by the binomial theorem). The polynomial for Fibonacci numbers is $x^2-x-1$ and here we need $(x-1)^2-(x-1)-1=x^2-3x+1$. So the recurrence formula is $f(n+2)=3f(n+1)-f(n)$, if I didn't make a mistake.