Question: 2015 Winter Midterm - 4
Consider strings consisting of the characters $a$, $b$, and $c$. Such a string is called valid,
if no two consecutive characters are equal. Thus, $abacbac$ is valid, whereas $abaccac$ is not
valid.
Let $n \geq 1$ be an integer and let $V_n$ be the number of valid strings of length $n$. Which of the following is true?
Let $n \geq 1$ be an integer and let $V_n$ be the number of valid strings of length $n$. Which of the following is true?
(a)
$V_n = 3^n - (n - 1) \cdot 3$
(b)
$V_n = 3^n - (n - 1) \cdot 3 \cdot 3^{n-2}$
(c)
$V_n = 3 \cdot 2^{n-1}$
(d)
None of the above.