I am trying to find a recurrence relation for the following 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.

So far, what i have come up with is $h(n) = h(n-1)+h(n-2)+2^{n-2}+2^{n-3}$, but when I try to solve that, I end up with non-whole number eigenvalues. Then, I tried the recurrence relation $h(n) = h(n-1)+2^{n-2}+2^{n-3}$, but when I solved I did not get an equation that matched the cases I computed by hand. Is my recurrence relation wrong or or am I solving wrong? Any help would be great!


This is an odd problem, because it seems easier to find a closed expression for $h(n)$ than a recurrence relation!

After all, how many words of length $n$ don't meet the criteria? Such a word can start with any number of B's. But once it hits the first A, it needs to alternate between A and B to avoid having either an AA or an ABB. Since there are $n+1$ words of length $n$ that satisfy that (starting with between $0$ and $n$ B's), $$h(0)=h(1)=0\\h(n)=2^n-n-1\quad\text{for }n\ge2$$

So, let's work backwards from here and come up with a recurrence relation. To find $h(n+1)$, we can start with a term of $2h(n)$ since every $n$ letter word that contains an AA or an ABB can either have an A or a B at the end and will still obviously contain that substring. So how many $n+1$ letter words wouldn't meet the criterion if you took off its last letter? Just $n$ of them. For instance, the six 7-letter words of that type are BBBBBAA, BBBBABB, BBBABAA, BBABABB, BABABAA, and ABABABB. You can see how we formed them by thinking about the previous paragraph. so a recurrence relation would be $$h(1)=0\\h(n+1)=2h(n)+n\quad\text{for }n\ge1$$ As to how you'd come up with that before the closed form, your guess is as good as mine. ^_^

  • $\begingroup$ Why would it been avoiding AA and ABB? $\endgroup$ – cpks18 Dec 10 '19 at 21:05
  • $\begingroup$ If you follow an A with another A, then there's an AA, and if you follow that AB with a B, then you have an ABB. So every A has to be followed by a B, and every B after you've seen an A has to be followed by an A. $\endgroup$ – Matthew Daly Dec 10 '19 at 21:07
  • $\begingroup$ Ok I understand that! However, do you think there is a way to devise a recurrence relation rather than an expression? $\endgroup$ – cpks18 Dec 10 '19 at 21:11
  • $\begingroup$ @cpks18 I added a recurrence relation part to my solution. $\endgroup$ – Matthew Daly Dec 10 '19 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.