Proving an equation for the number of "sentences" using $k$ letters

Question

Suppose there is a language of three words $W_1=a$, $W_2=ba$, $W_3=bb$. Let $N(k)$ be the number of sentences using exactly $k$ letters. Then there is only one sentence with a single letter, $(a)\,$ so $N(1) = 1$. Furthermore, $N(2) = 3$ since there are three possible sentences with two letters: ($a.a/ ba/ bb$). Also $N(3) = 5$, with the possible sentences being $(a.a.a/ a.ba/ ba.a/ a.bb/ bb.a)$. No space is allowed between words.

I'm trying to show that $$(*)\quad\quad N(k) = N(k-1) + 2N(k-2),\,\,k=2,3\ldots,$$ where $N(0)=1$.

I'm going to use a combinatorial argument, but before that, I just want to check $(*)$ is correct for some $k$.

For instance, if $k=4$, $(*)$ implies $N(4) = N(3)+2N(2)=5+2\cdot 3=11$, i.e. there are 11 four-letter sentences. However, as far as I can see, the possible four-letter sentences are $$(a.a.a.a/ a.a.ba/ a.ba.a/ ba.a.a/ a.a.bb/ a.bb.a/ bb.a.a/ ba.bb/ bb.ba),$$ 9 and not 11 as $(*)$ predicts.

I must be missing something...

Answer 1

You're missing $\ baba\ $ and $\ bbbb\ $.

Answer 2

There are really $11$ sentences on $4$ letters – you forgot $ba.ba$ and $bb.bb$.

As for the actual question, an admissible sentence can be unambiguously broken up into its words by working from the left, since the words form a prefix code. A word on $k$ letters thus either

• begins with $W_1=a$, and removing it produces a sentence on $k-1$ letters
• begins with $W_2=ba$ or $W_3=bb$, and removing the appropriate word produces a sentence on $k-2$ letters

Thus $N(k)=N(k-1)+2N(k-2)$.