Find a recursive definition of this sequence I always have some difficulty with problems of this type, and I was wondering if there was a typical trick that makes it reasonable. 
Let $W_n$ be the number of words of length $n$ formed with the letters $A$ and $B$ such that


*

*There are no words that contain sequences of $A$s with length exactly 2

*There are no words that contain sequences of $B$s with length exactly 2 or 3. 
Examples of words: $AAAB, ABABABA, ABBBBAAABA$, and of non-words: $AAB, ABBBA$, etc.
These "recursion with constraints" type problems always cause me difficulty. I want to write $W_n = f(W_{n-1}, W_{n-2}, \ldots, W_{n-k})$ for some fixed $k$. I tried to break it into cases based on what the last letter is, so $W_n = A_n + B_n$ where $A_n$ is the number of words of length $n$ that end in $A$ and $B_n$ defined similarly. Then getting recursive definitions for $A_n$ in terms of some $B_{n-k_i}$ and $W_{n-k_j}$ and likewise recursive definitions for $B_n$ produces a whole mess of terms that don't cancel even when you get these $W_{n-11}$ terms showing up. Surely I'm missing the trick? 
 A: We can write down an infinite recursion and then simplify.
Let $A_n$ be the number of such sequences ending in A, and $B_n$ be the number of such sequences ending in B. We count the empty string in both.
Then, for $n \ge 1$, we have
$$
   A_n = B_{n-1} + B_{n-3} + B_{n-4} + B_{n-5} + \dotsb
$$
because we can add A or AAA or AAAA or AAAAA to the end of a string ending in B, but not both. So for $n \ge 2$, we have
\begin{align}
A_n - A_{n-1} &= (B_{n-1} + B_{n-3} + B_{n-4} + B_{n-5} + \dotsb) - (B_{n-2} + B_{n-4} + B_{n-5} + B_{n-6} + \dotsb) \\
  &= B_{n-1} - B_{n-2} + B_{n-3}. \\
A_n &= A_{n-1} + B_{n-1} - B_{n-2} + B_{n-3}.
\end{align}
We can do the same thing for $B_n$, except that $B_n$ won't have an $A_{n-3}$ term in the recurrence. For $n\ge 2$, we get
\begin{align}
  B_n - B_{n-1} &= (A_{n-1} + A_{n-4} + A_{n-5} + \dotsb) - (A_{n-2} + A_{n-5} + A_{n-6} + \dotsb) \\
   &= A_{n-1} - A_{n-2} + A_{n-4}. \\
B_n &= A_{n-1} + B_{n-1} - A_{n-2} + B_{n-4}.
\end{align}
This is already enough to make the problem a finite linear recurrence, but we can still try to simplify it further.

For $n \ge 1$, we have $W_n = A_n + B_n$, so we have
$$
  W_n = 2W_{n-1} - W_{n-2} +B_{n-3} + A_{n-4}
$$
by adding the two equations. Unfortunately, we still have a mismatched $A$ and $B$ to deal with here.
Expanding $B_{n-3}$ and $A_{n-4}$ out using their recurrences, we get
\begin{align}
W_{n} &= 2W_{n-1} - W_{n-2} + (W_{n-4} - A_{n-5} + A_{n-7}) + (W_{n-5} - B_{n-6} + B_{n-7}) \\
  &= 2W_{n-1} - W_{n-2} + W_{n-4} + W_{n-5} - A_{n-5} - B_{n-6} + W_{n-7}
\end{align}
which again has a mismatched $A$ and $B$, but now in the reverse order. So if we subtract $W_{n-2}$ from both sides, we get
\begin{align}
W_n - W_{n-2} &= (2W_{n-1} - W_{n-2} + W_{n-4} + W_{n-5} - A_{n-5} - B_{n-6} + W_{n-7}) \\&\quad - (2W_{n-3} - W_{n-4} + B_{n-5} + A_{n-6}) \\
&= 2W_{n-1} - W_{n-2} - 2W_{n-3} + 2W_{n-4} - W_{n-6} + W_{n-7}
\end{align}
and the final recursion is $W_n = 2W_{n-1} - 2W_{n-3} + 2 W_{n-4} - W_{n-6} + W_{n-7}$. (This may not fly for small $n$ - in particular, $W_0 \ne A_0 + B_0$ - but for $n> 7$ all the manipulations above are valid.)
A: Maybe this graph will be of assistance:

You want to count the walks of length $n$ starting from the left-most state and ending up in any of the blue states.
A: Let $w(n)$ be the number of qualifying words of length $n$.

Then $w$ satisfies the recursion 
$$w(n)=2w(n-1)-2w(n-3)+2w(n-4)-w(n-6)+w(n-7)$$
for $n\ge 8$, with initial values
\begin{align*}
w(0)&=1\\
w(1)&=2\\
w(2)&=2\\
w(3)&=3\\
w(4)&=6\\
w(5)&=11\\
w(6)&=18\\
w(7)&=30\\
\end{align*}
The above recursion can be derived as follows . . .

Define functions $a_1,a_3,b_1,b_4$ by


*

*$a_1(n)$ is the number of qualifying words of length n for which the last constant block is exactly "A".

*$a_3(n)$ is the number of qualifying words of length n for which the last constant block ends with "AAA" (i.e., at least $3$ consecutive occurrences of "A").$\\[6pt]$

*$b_1(n)$ is the number of qualifying words of length n for which the last constant block is exactly "B".

*$b_4(n)$ is the number of qualifying words of length n for which the last constant block ends with "BBBB" (i.e., at least $4$ consecutive occurrences of "B").


Then we get the following linked recursion:
\begin{align*}
w(n)&=
\begin{cases}
1\;\text{if}\;n=0\\
a_1(n)+a_3(n)+b_1(n)+b_4(n)\;\text{if}\;n > 0\tag{eq1}\\
\end{cases}
\\[4pt]
a_1(n)&=
\begin{cases}
0\;\text{if}\;n<1\\
1\;\text{if}\;n=1\\
b_1(n-1)+b_4(n-1)\;\text{if}\;n > 1\tag{eq2}\\
\end{cases}
\\[4pt]
a_3(n)&=
\begin{cases}
0\;\text{if}\;n<3\\
1\;\text{if}\;n=3\\
b_1(n - 3) + b_4(n - 3)+a_3(n-1)\;\text{if}\;n > 3\tag{eq3}\\
\end{cases}
\\[4pt]
b_1(n)&=
\begin{cases}
0\;\text{if}\;n<1\\
1\;\text{if}\;n=1\\
a_1(n-1)+a_3(n-1)\;\text{if}\;n > 1\tag{eq4}\\
\end{cases}
\\[4pt]
b_4(n)&=
\begin{cases}
0\;\text{if}\;n<4\\
1\;\text{if}\;n=4\\
a_1(n - 4) + a_3(n - 4)+b_4(n-1)\;\text{if}\;n > 4\tag{eq5}\\
\end{cases}
\\[4pt]
\end{align*}
Applying the linked recursion, we get
\begin{align*}
w(0)&=1\\
w(1)&=2\\
w(2)&=2\\
w(3)&=3\\
w(4)&=6\\
w(5)&=11\\
w(6)&=18\\
w(7)&=30\\
\end{align*}
Next, we unlink the linked recursion . . .

Using $(\text{eq}2)$, we can eliminate $a_1$.

Then, using $(\text{eq}4)$, we can eliminate $b_1$.

Then, using $(\text{eq}5)$, we can eliminate $a_3$.

Based on the eliminations, from $(\text{eq}1)$ we get
$$
w(n)=2b_4(n+3)-4b_4(n+1)+3b_4(n)+2b_4(n-1)-3b_4(n-2)+b(n-3)+b(n-4)-b_4(n-5)
$$
for $n\ge 6$, and from $(\text{eq}3)$ we get
$$
b_4(n)=2b_4(n-1)-2b_4(n-3)+2b_4(n-4)-b_4(n-6)+b_4(n-7)
$$
for $n\ge 8$.

Since shifts of $b$ satisfy the same recursion as $b$, and since $w$ is a linear combination of $b$ and shifts of $b$, it follows that $w$ also satisfies the same recursion as $b$, hence we get
$$w(n)=2w(n-1)-2w(n-3)+2w(n-4)-w(n-6)+w(n-7)\tag{eq6}$$
for $n\ge 13$.

We already have the values of $w(n)$ for $0\le n\le 7$.

Applying the linked recursion, we can get the values of $w(n)$ for $8\le n\le 12$, and it can then be verified that $(\text{eq}6)$ fails for $n=7$, but holds for $8\le n\le 12$, hence holds for all $n\ge 8$.
A: Here is a rewriting of above work using automaton and generating functions. The associated grammars need to be unambiguous; if not, because of the copies, the numbers obtained will be higher than the right ones.

By the second diagram, one may write 
$A = x + xC + xD$ where :
$A = a_1x + a_2x^2 + a_3x^3 + ... $is the generating function (or the string index) for words that ends exactly in $0$. We have similar expressions for B, C and D.
Similarly, the other three equations are:
$B = x^3 + xB + x^3C + x^3D $
$C = x + xA + xB$
$D = x^4 + x^4A + x^4B + xD$
Here $x$ stands for $0$ or $1$, $x^3$ covers the bit string $000$; $x^4$ covers the bit string $1111$; 
The above (second) system easily solves to the same solution as the first diagram :

here (for example), $x + {x^3 \over 1-x } $ encodes the set { 0, 000, 0000, 00000, ....}
the two equations are 
$ A+B = {x-x^2+x^3 \over 1-x } ( C + D + 1 ) $ and
$ C+D = {x-x^2+x^4 \over 1-x } ( A + B + 1 ) $
that easily solves to $ W=A+B+C+D= {2x - 2x^2 - x^3 + 4x^4 -x^5 -2x^6 + 2x^7 \over 1 - 2x + 2x^3 - 2x^4 + x^6 - x^7} $
$= 2+2x +3x^2 +6x^3 +11x^4 +18x^5+30x^6 +50x^7 +85x^8 +143x^9+ 241x^{10} + ...$
The denominator encodes the required recurrence.
