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. ^_^