Question: 2018 Winter Final - 8
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 \geq 2$, what is the number of valid strings of length $n$?
For any integer $n \geq 2$, what is the number of valid strings of length $n$?
(a)
$4 \cdot 3^{n}$
(b)
$4^{n} - 4(n-1)$
(c)
$4 \cdot 3^{n-1}$
(d)
$4^{n} - 4n$