# Finding a Recurrence Relation and Solving

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