Find and solve the recurrence relation for the number of n-letter words composed from letters A, B, C and D such that no A comes after any B.
What I learn in the class is,
$$ A = a_{n-1} $$
$$ B = 3^{n-1} $$
$$ C = a_{n-1} $$
$$ D = a_{n-1} $$
why B is different from other? Also how can I solve this one using recurrence relation? Thanks in advance!
Solving Recurrence Relation for the number of n-letter words
discrete mathematicsrecurrence-relations
Best Answer
The difference for $B$ is because once we use a $B$, we can't have any $A$'s in the rest of the string (if we start with any other letter, then any good string works). I'm assuming the third line should be $C =a_{n-1}$, and that this means "the number of $n$-letter good strings starting with $C$ is $a_{n-1}$." This justification comes from the fact that, if we start with $C$ (or $A$ or $D$), then to make a good string, we just add on another good string of length $n-1$. But if we start with $B$, then we can't just add on a shorter good string because that might contain $A$; instead, we just want to count how many strings we can make that don't use $A$; this is just $3^{n-1}$.
Summing over all cases gives the recurrence relation $a_n = 3a_{n-1} + 3^{n-1}$.