5. with the help of the three letters I, M, O words of length $n$ are formed. How many such words of length $n$ are there in which no neighboring M's occur?

## Solution
We call a word admissible if it does not contain two adjacent M's. Let $a_{n}$ be the number of admissible words of length $n$ and $b_{n}$ the number of admissible words of length $n$ that do not start with a $\mathrm{M}$. Take an allowed word of length $n$ and remove the first letter, the remaining word is called a stump. The stump is a valid word of length $n-1$. If the word does not begin with an M, then there is no restriction on the stump, i.e. $a_{n-1}$ possibilities. However, if it begins with an M, the stub must not also begin with M, leaving $b_{n-1}$ possibilities. This yields the recursion equations $a_{n}=2 a_{n-1}+b_{n-1}$ and $b_{n}=2 a_{n-1}$. Combining these equations immediately yields

$$
a_{n}=2 a_{n-1}+2 a_{n-2}, \quad n \geq 3
$$

The characteristic polynomial of this recurrence equation is $x^{2}-2 x-2$ and has the zeros $1 \pm \sqrt{3}$. There are therefore real constants $A$ and $B$ with

$$
a_{n}=A(1+\sqrt{3})^{n}+B(1-\sqrt{3})^{n} .
$$

Inserting $a_{1}=3$ and $a_{2}=8$ yields the equations $3=(1+\sqrt{3}) A+$ $(1-\sqrt{3}) B$ and $8=(4+2 \sqrt{3}) A+(4-2 \sqrt{3}) B$ for $A$ and $B$. This results in $A=(3+2 \sqrt{3}) / 6$ and $B=(3-2 \sqrt{3}) / 6$, so the explicit formula applies

$$
a_{n}=\frac{1}{6}\left[(3+2 \sqrt{3})(1+\sqrt{3})^{n}+(3-2 \sqrt{3})(1-\sqrt{3})^{n}\right] .
$$

The first few values can be found in the table below:

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $a_{n}$ | 3 | 8 | 22 | 60 | 164 | 448 | 1224 |