Question: 2016 Fall Final - 10
Consider strings of characters, each character being $a$, $b$, $c$, $d$, or $e$, in which no two
consecutive characters are equal. Let $S_n$ be the number of such strings having length $n$. Which
of the following is true for $n \geq 1$?
(a)
$S_n = 5 \cdot 4^{n-1}$
(b)
$S_n = 5 \cdot 4^{n-2}$
(c)
$S_n = 5^{n} - 5(n-1) \cdot 4^{n-2}$
(d)
$S_n = 5^{n} - 5(n-1) \cdot 4^{n-1}$