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?
Answer: 4 * 3^(n-1)
Attempt: I took n=4 for a string for the word "baad". Since, a valid string does not have "aa" I counted the possible ways to write "baad" without haveing 2 consecutive a's.
I did this by: 2!*(3C2) and got 6. My answer is way off. I'm assuming my logic doesn't make sense. Can someone please explain to me how to logically approach this.