How many words of length $n$ is it possible to create from $\{a,b,c\}$ without any “$c$”s after a “$b$”?

Question

This post is a duplicate of this post.

The question is,

How many words of length $n$ is it possible to create from $\{a,b,c\}$ without any “$c$”s after a “$b$”?

For example, the string $\color{blue}{\text{aabac}}$ is allowed but $\color{blue}{\text{cc}\color{red}{\text{bc}}\text{ab}}$ is not allowed because it contains $\text{bc}$ in that order. It could, however include $\text{cb}$.

I worked it for small values of $n$, and searched the resulting sequence on OEIS.

I have been told of a method by forming a recurrence relation, which I have to still think upon, but the question is why is it related to even indexed fibonacci sequence? Is there any natural interpretation of this? I was amazed to see so many equivalent definitions of this problem in the OEIS page and this definition is one of them. I would be glad to see some different answers to this problem.

---

Here is another related post.

Answer 1

Let $a_n$ be the number of such strings of length $n$, $b_n$ be the number of such strings which end with b, and $c_n$ the number of such strings which do not end with b. Then

• $a_n = b_n+c_n$, since these are the total number of such strings with length $n$
• $b_n = a_{n-1}$, since you can take a string of length $n-1$ and put a b on the end, and this gives $a_n = a_{n-1}+c_n$
• $c_n = b_{n-1}+2c_{n-1}$, since you can take a string of length $n-1$ ending in b and put an a on the end or you can take a string of length $n-1$ not ending in b and put an a or a c on the end, and this gives $c_n = a_{n-1}+c_{n-1}$

$c_n = a_{n-1}+c_{n-1}$ and $a_n = a_{n-1}+c_n$ look Fibonacci-like. Suppose we define $d_n$ such that $d_{2n-1}=c_n$ and $d_{2n}=a_n$. Then we have $d_{2n-1}=d_{2n-2}+d_{2n-3}$ and $d_{2n}=d_{2n-1}+d_{2n-2}$ so combined $$d_{n}=d_{n-1}+d_{n-2}$$ which is the Fibonacci recurrence.

You also have to check the initial terms: $d_0=a_0=1$, $d_1=c_1=2$, $d_1=a_1=3$, so $d_n$ is the Fibonacci sequence offset by two positions, and $a_n=d_{2n}$ is the even terms of the Fibonacci sequence again with an offset.

Answer 2

One can quickly derive the recurrence relation for even-indexed Fibonacci numbers :

$$F_{2k+2}=F_{2k+1}+F_{2k}$$ $$F_{2k+2}=(F_{2k}+F_{2k-1})+F_{2k}$$ $$F_{2k+2}=(F_{2k}+(F_{2k}-F_{2k-2}))+F_{2k}$$ $$\Rightarrow \boxed{F_{2k+2}=3F_{2k}-F_{2k-2}} \tag{$k \ge 1$}$$

where $F_{0}=0$, $F_{2}=1$, $F_{4}=3$, $F_{6}=8$, $\ldots$

The problem satisfies the same recursive relation as given by @lulu : $$\boxed{T_{n+1}=3T_{n}-T_{n-1}}$$

Also note, $T_1=3$, $T_2=3^2-1=8$.

The recurrence relation as well as the terms of sequence match. Hence the two sequences are identical.