Recurrence relation for string of 1's, 2's and 4's with constraints. The assignment

(a) Find a recurrence relation for $a_n$, the number of sequences of 1s, 2s and 4s summing to $n$ with the subsequence 421 not allowed.
(b) Repeat part (a) but now with the requirement that you cannot have the subsequence 22.

Answer
$$\tag{a}\quad a_n=a_{n-1}+a_{n-2}+a_{n-4}-a_{n-7}$$
$$\tag{b}\quad a_n=a_{n-2}+2a_{n-5}+a_{n-8}$$
How did my teacher get (b)? Since you cant have 22, shouldn't it be $a_n=a_{n-1}+a_{n-2}$?
 A: First method.
For the first question we get the following system of equations in the
corresponding generating functions:
$$Q - 1 = Q (z + z^2) + Q_{4} z + Q_{42} z^2,$$
$$Q_{4} = Q z^4 + Q_4 z^4 + Q_{42} z^4,$$
$$Q_{42} = Q_{4} z^2,$$
$$Q_{421} = Q_{42} z + Q_{421} (z^4 + z^2 + z).$$
Solving this we obtain
$$A(z) = Q + Q_4 + Q_{42} =
\frac{1}{1-z-z^2-z^4+z^7}.$$
Extracting coefficients from (here we take $n\ge 7$)
$$[z^n] A(z) (1-z-z^2-z^4+z^7) = [z^n] 1 = 0$$
we find
$$a_n - a_{n-1} - a_{n-2} - a_{n-4} + a_{n-7} = 0$$
or
$$a_n = a_{n-1} + a_{n-2} + a_{n-4} - a_{n-7}$$
as claimed.  We need the initial values $a_0$ to $a_6$ in order to use
this recurrence.   The coefficient extractor yields  zero for negative
indices so we may start the recurrence  with $a_0 = 1$ and compute the
next  six values  by setting  the contribution  from those  indices to
zero, getting $1, 1, 2, 3,\ldots$

Second method.
Let $B(z)$ be the generating function  of the weighted strings that do
contain $421.$ We obtain from first principles
$$A(z) + B(z) = \frac{1}{1-z-z^2-z^4}.$$
We also have by classifying according to the first ocurrence of the pattern $421$ that
$$B(z) = A(z) z^7 \frac{1}{1-z-z^2-z^4}.$$
Solving  for $A(z)$  yields  the same  answer as  before.  We get  the
the initial segment as shown:
$$1+z+2\,{z}^{2}+3\,{z}^{3}+6\,{z}^{4}+10\,{z}^{5}+18\,{z}^{6}+30\,{z}^{7}
\\+53\,{z}^{8}+91\,{z}^{9}+159\,{z}^{10}
\\+274\,{z}^{11}+476\,{z}^{12}+823\,{z}^{13}+\cdots$$
The  following Maple  code  shows  how to  solve  the  two systems  of
equations and presents an enumeration routine whose output matches the
generating function $A(z)$ (tested up to $n=13.$)

sys := [Q-1 = Q*(z+z^2) + Q4*z + Q42*z^2,
        Q4 = Q*z^4 + Q4*z^4 + Q42*z^4,
        Q42 = Q4*z^2,
        Q421 = Q42*z + Q421*(z^4+z^2+z)];

sol := op(1, solve(sys, [Q, Q4, Q42, Q421]));

gf := factor(subs(sol, Q + Q4 + Q42));

sys2 := [A + B = 1/(1-z-z^2-z^4), B = A * z^7/(1-z-z^2-z^4)];

sol2 := op(1, solve(sys2, [A, B]));

gf2 := subs(sol2, A);

ENUM :=
proc(X)
option remember;
local len, str, gf, d, pos, wt;

    gf := 1; d := [0]; len := 1;

    while len <= X do
        str := subs([0=1, 1=2, 2=4], d);

        for pos to len - 2 do
            if str[pos] = 4 and
            str[pos+1] = 2 and str[pos+2] = 1 then
                break;
            fi;
        od;

        if len < 3 or pos = len - 1 then
            wt := add(q, q in str);

            if wt <= X then
                gf := gf + z^wt;
            fi;
        fi;

        for pos to len do
            if d[pos] < 2 then
                d := subsop(pos = d[pos] + 1, d);
                break;
            else
                d := subsop(pos = 0, d);
            fi;
        od;

        if pos = len + 1 then
            len := len + 1;
            d := [op(d), 0];
        fi;
    od;

    gf;
end;

The     second    method     was     presented     at    this     MSE
link.
