Question: How can I force subs to do all substitutions

I was working through an old text book, trying to understand a different problem.  I came across this problem in an exercise set and thought it was simple.  Until I tried it.

The difficlty I had was in using subs to substitute all values.  I had to use subs 2 or 3 times to get all substitutions.  How can I avoid this?

## Prove if F is the fibonacci sequence,
restart;
with(combinat, fibonacci):
F := n -> fibonacci(n);  ## F(n+1) = F(n)+F(n-1); F(1) = 1;
## the problem
P := n-> F(n+1)*F(n+2) - F(n)*F(n+3);
##
check_low := proc(n)
    local idx;
    for idx to n do
        print(P(idx),(-1)^idx);
    end do;
end proc;
check_low(1);
check_low(2);
check_low(3);
check_low(4);

## Assume true for n=k
A := P(k) = (-1)^k;

notation := { F(k)   = a,
              F(k+1) = b,
              F(k+2) = c,
              F(k+3) = d,
              F(k+4) = e };

## some fibonacci definitions
fibs := [ e = c + d,  d = b + c, c = a + b ];

eq1 := subs(notation,A);
eq1 := subs(fibs,eq1);
eq1 := subs(fibs,eq1);  ## have to repeat to get only a and b in the expression

eq2 := subs(notation,P(k+1));
eq2 := subs(fibs, eq2);
eq2 := subs(fibs, eq2);
eq2 := subs(fibs, eq2);  ## have to repeat to get only a and b in the expression
## Reduce eq2 to (-1)^(k+1)
simplify(eq2 = -lhs(eq1));
verify(eq2, -lhs(eq1), equal);
evalb(eq2); simplify(%);  ## Ah, this is why I need equal in verify.
evalb(-lhs(eq1)); simplify(%);

testeq(eq2, -lhs(eq1));