Question

For integer n ≥ 1, let h(n) be the number of length n words consisting of A’s and B’s, that contain either at least an “AA”, or at least an “ABB”. Find a recurrence relation satisfied by h(n) (with necessary initial conditions) and solve it. (Previous answers to this question have been incorrect)

Answer 1

ANSWER:

For integer n ≥ 1, let h(n) be the number of length n words consisting of A’s and B’s

Let h(n) be such no of length n words.

There are 3 cases

Case 1- word starts with B ,then h(n) will be h(n-1)

Case 2-word starts with AA then all remaining n-2 length words will be accepted which is 2^n-2 .

Case 3-word starts with AB Here ther are 2 cases

Case 3.a- word starts with ABB then n-3 length words will be accepted which is 2^n-3

Case 3.b- word starts with ABA then h(n) will be h(n-2) because third character of this string is A,So valid string can also be started from this third character.

So recurrence relation will be

h(n) = h(n-1) + h(n-2) + 2^n-2 + 2^n-3

Here base case is

h(0)=0

h(1)=0 (which means that length of 0 and 1 words that satisfy above condition is zero).

h(2)=1 and so on.