Solution: 2015 Winter Midterm - 4
Author: Michiel SmidQuestion
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.
Solution
The first letter can be anything. So there are 3 choices.
The second letter cannot be the same as the first letter. So there are 2 choices.
For the third letter, there are 2 choices. Same as the second letter.
We can continue this pattern until the end of the string.
Thus, there are $3 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2$ valid strings.
Rewriting this, we get $V_n = 3 \cdot 2^{n-1}$.