Determine an, the number of words of length n on the alphabet {a, b, c} which do not contain the substring ab. For instance, a3 = 21 since there are 21 such words with 3 letters, namely: aaa aac aca acb acc baa bac bba bbb bbc bca bcb bcc caa cac cba cbb cbc cca ccb ccc.

Solution.

There are $3^n$ different words of length $n$ over this alphabet {a,b,c}.

1){b.......} or {c........}

If a string begins with b or c, then we are left with a string of length n−1, which can start with any character. There are an-1 strings of this type.

We have $2•a_{n-1}$ strings of this kind.

2) {aa.......} or {ac......}

If a string begins with a, and the second letter must be a or c, then you are left with a string of length n−2, which can start with any character. There are an-2 strings of this type.

We have $2•a_{n-2}$

strings of this kind.

3) {aab.....}

Subtract the number of lines of this type.

We have $a_{n-3}$ strings of this kind.

4) So, we have answer

$a_n=2•a_{n-1}+2•a_{n-2}-a_{n-3}$

$a_1=3, a_2=8, a_3=21.$

For a example, $a_4=2•21+2•8-3=55.$