Using only letters A B & C, how many different messages of length N can you type? with the constraint that ABC cannot appear anywhere in the
string. For example, typing BACBBC would be fine, but typing BC
ABCB would not. With this constraint, how many different messages of length N can you type? Does anyone know how to solve it using recursion?
N is the length so my solution so far say if it starts with an B or C then there are f(N-1) ways the rest of the string could be arranged. If it starts with an A then there are 4*f(N-3) ways we can arrange it. Therefore:
f(N) = f(N-1) + f(N-1) + 4*f(N-3).... this is incomplete can anyone point me in the right direction?