How many "words" of length n is it possible to create from {a,b,c,d} without any "a"s after a "b"? I think this is a hard question and I didn't come up with a solution. Could you please give me a hint or approach?
For instance, "bdca" is not ok, but "aabcd" is ok.
It is somehow similar to this question, but with some differences.
Thanks in advance.

Hint
$\sum_{k=1}^n [f(k) \times g(k)].$
$f(k)$ is the # of possible sequences of length $k$, where the very first occurrence of the letter $b$ is on the $k$-th letter.
Note that this categorization facilitates mutually exclusive groupings.
$g(k)$ is the # of possible sequences of length $(n-k)$ where the letter $a$ is excluded from this sequence.
Two items need special handling:
What happens if the first $b$ in the sequence is on the last (i.e. $n$-th) letter?
What happens if the sequence does not contain any $b$'s.
