How many words of length $n$ over the alphabet $\{a,b\}$ such that the sub-word $bb$ does not appear?

Question

What is the best way to find solution to this question? I was trying to write down all the options for $n=2,3$, and then I removed the options which included $bb$ together. But that does not work.

Answer 1

Let $x_n$ be the number of such words that ends in $a$ and let $y_n$ be the number that end in $b$.

Then $x_0=y_0=0$, $x_1=y_1=1$, $$x_{n+2} = 2x_n + y_{n}$$ (since a word that ends in $a$ can be followed by $ba$ or $aa$; whereas one that ends in $b$ must be followed by $aa$). Find a similar recurrence for $y_n$ and go from there.

Answer 2

Let $a_n$ be the number of admissible words of length $n$.

Any word of length $1$ is admissible. Any word of length $2$ is admissible except $bb$. Since there are two ways to fill each position in a word without restriction, we have \begin{align*} a_1 & = 2\\ a_2 & = 3 \end{align*} Any admissible word must end in $a$ or $b$. Any admissible word of length $n$ that ends in $a$ can be formed by appending an $a$ to an admissible word of length $n - 1$, and any admissible word of length $n - 1$ can be extended to a word of length $n$ by appending an $a$ to it. Hence, there are $a_{n - 1}$ admissible words of length $n$ that end in $a$. Any admissible word of length $n \geq 2$ that ends in $b$ must end in $ab$. Thus, any admissible word of length $n$ that ends in $b$ can be formed by appending $ab$ to an admissible word of length $n - 2$, and any admissible word of length $n - 2$ can be extended to an admissible word of length $n$ by appending an $ab$. Hence, there are $a_{n - 2}$ admissible words that end in $b$. Therefore, we have the recurrence relation $$a_n = a_{n - 1} + a_{n - 2}, n \geq 3$$ The first few terms of this sequence are $2, 3, 5, 8, 13, 21, 34, 55, 89, ...$. Notice that $a_n = F_{n + 2}$, where $F_n$ is the $n$th Fibonacci number.

Alternatively, for the recurrence, any admissible word must begin with $a$ or $ba$. If it begins with $a$, it can be extended to an admissible word of length $n \geq 3$ by appending an admissible word of length $n - 1$, of which there are $a_{n - 1}$. If it begins with $ba$, it can be extended to an admissible word of length $n$ by appending an admissible word of length $n - 2$, of which there are $a_{n - 2}$. Hence, we again obtain the recurrence $$a_n = a_{n - 1} + a_{n - 2}, n \geq 3$$

Answer 3

I had a similar idea than the one in Bjørn's answer:

Define $a_n$ the number of suitable words ending with an "a" having the length $n$. And $b_n$ the number of words ending with a "b". "c" is the number of words in total ($c_n=a_n+b_n).$

A word of the length $n+1$ with $n\geq 1$ is formed by adding one letter to a existing word with the length $n$. So:

• A word ending with an "a" can be formed by either adding an "a" to a word ending with "a" or a word ending with "b". Therefore:
  $a_{n+1}=c_n=a_n+b_n$
• A word ending with a "b" can only be formed by adding a "b" to a word ending with "a". Therefore:
  $b_{n+1}=a_n$

For values $n\geq 1$ this leads to:

$c_{n+2}=a_{n+2}+b_{n+2}=c_{n+1}+a_{n+1}=c_{n+1}+c_n$

This is the same rule as for the Fibonacci sequence ($F_n$).

For $n \in \{0, 1, 2\}$ we have to find out the number of words separately: $c_0=0$, $c_1=2$, $c_2=3$

$c_1$ and $c_2$ are the 3rd and 4th element of the Fibonacci sequence and the rule for calculating the next element is the same so:

$c_n=\begin{cases} 0\text{ for }n=0\\ F_{n+2} \text{ for } n>0\end{cases}$

While $F_n$ is the Fibonacci sequence.

Edit

It is of course a question of the definition if a "word with zero letters" exists or not.

If yes, this word does not contain the sequence "bb" so $c_0=1=F_{0+2}$ also applies for $n=0$.