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? 

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.)
