# Counting strings: Determine the number of valid strings of length n

Question: Consider strings consisting of characters, where each character is an element of {a; b; c; d}. Such a string is called valid, if it does not contain aa, it does not contain bb, it does not contain cc, and it does not contain dd. For any integer n >= 2, what is the number of valid strings of length n?

• I don't understand what you mean by "the $aa$ string". Say the string has length $2$. Then there are four candidates for the first letter and, having chosen the first letter, there are three candidates for the second. Hence the answer is $4\times 3=12$. – lulu Nov 25 '18 at 19:53
• I don't understand any of your calculations...they don't appear to be connected to the problem. Look at my calculation for length $2$. Now do it for length $3$. You should see that you again have three choices for the third character. Continue in this way. – lulu Nov 25 '18 at 19:54
• You have four choices for the first slot, then three for the second (since you can't match the first), then three for the third (since you can't match the second). Hence $4\times 3^2$. – lulu Nov 25 '18 at 20:11