[ Fibonacci words ]

Find the number of words of length 10, consisting only of the letters "a" and "b" and not containing two consecutive "b" letters in their sequence.

#
Let $\mathrm{a}_{\mathrm{n}}$ denote the number of words of length n, consisting only of the letters "a" and "b" and not containing two consecutive "b" letters. In the sequence $\mathrm{a}_{1}, \mathrm{a}_{2}, \ldots, \mathrm{a}_{\mathrm{n}}$, express each subsequent term in terms of the previous ones.

## Solution

Let $\mathrm{a}_{\mathrm{n}}$ denote the number of words of length n, consisting only of the letters "a" and "b" and not containing two consecutive "b" letters. Thus, we find $\mathrm{a}_{1}=2$, $\mathrm{a}_{2}=3$. We will show that $\mathrm{a}_{\mathrm{n}}$ can be expressed in terms of $\mathrm{a}_{\mathrm{n}-1}$ and $\mathrm{a}_{\mathrm{n}-2}$. The number of words of length n, not containing two consecutive "b" letters and starting with the letter "a", is $\mathrm{a}_{\mathrm{n}-1}$, since after the first letter, any word of length n-1, not containing two "b" letters in a row, can follow. Suppose a word of length n starts with the letter "b". If this word does not contain two consecutive "b" letters, then the second letter is "a", and any word of length n-2, not containing two consecutive "b" letters, can follow. Thus, the number of words of length n, not containing two consecutive "b" letters and starting with the letter "b", is $\mathrm{a}_{\mathrm{n}-2}$. Therefore, we have shown that $\mathrm{a}_{\mathrm{n}}=\mathrm{a}_{\mathrm{n}-1}+\mathrm{a}_{\mathrm{n}-2}$. Now we sequentially calculate $\mathrm{a}_{3}=\mathrm{a}_{2}+\mathrm{a}_{1}=3+2=5$, $\mathrm{a}_{4}=\mathrm{a}_{3}+\mathrm{a}_{2}=5+3=8$, and so on, $\mathrm{a}_{10}=\mathrm{a}_{9}+\mathrm{a}_{8}=144$. Notice that the resulting numbers $\mathrm{a}_{\mathrm{n}}$ are the well-known Fibonacci numbers.

## Answer

144