, 2011

Let $a_n$ be the number of admissible words with $n$ letters; then $a_0 = 1$ (the empty word), $a_1 = 3$ and $a_2 = 8$.

Then, if we add a letter at the end of a correct word with $n$ letters, we obtain either a correct word with $n+1$ letters, or a forbidden word of the form $XY$, with $Y$ a forbidden sequence with $k$ letters, $2 \le k \le n+1$ and $X$ a correct word with $n-k+1$ letters. So, the forbidden words with $n+1$ letters are at most $a_0 + a_1 + a_2 + \dots + a_{n-1}$, hence
$$a_{n+1} \ge 3a_n - (a_0 + a_1 + a_2 + \dots + a_{n-1}).$$
The above relation allows to prove inductively that $a_{n+1} > 2a_n$ ($*$), for every $n \ge 1$. Indeed, the base case is obvious, and if ($*$) is true for all the numbers from 0 to $n-1$, $n \ge 2$, then $a_n \ge 2^k a_{n-k}$, $0 \le k \le n-1$, whence
$$a_{n+1} \ge a_n \left( 3 - \left( \frac{1}{2^n} + \frac{1}{2^{n-1}} + \dots + \frac{1}{2} \right) \right) > 2a_n.$$
This shows that there are at least $2^n$ words of length $n$.