Solution: 2015 Winter Midterm - 4

Author: Michiel Smid

Question

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?

(a)

$V_n = 3 \cdot 2^{n-1}$

(b)

$V_n = 3^n - (n - 1) \cdot 3$

(c)

None of the above.

(d)

$V_n = 3^n - (n - 1) \cdot 3 \cdot 3^{n-2}$

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}$.