Find the number an of strings of length n over the alphabet

Find the number an of strings of length n over the alphabet A = {0,01,111}.

Find the number an of strings of length n over the alphabet A = {0,01, 111}.

Solution

Let anan be the number of bit strings of length nn containing a pair of consecutive 11\'s. In order to construct such a bit string, one could start with

Since these three cases are mutually exclusive and exhaust the possibilities for how such a string might start, we can apply the sum rule and write down the following recurrence relation valid for all n2;n2;

an=an1+an2+2n2an=an1+an2+2n2

(Recall that there are 2k2k bit strings on length kk).

Now for the initial conditions: