Solution: 2018 Winter Final - 8
Author: Michiel SmidQuestion
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$
Solution
The first character can be any of the 4 characters: 4
The second character can be any of the 3 characters that are not the first character: 3
The third character can be any of the 3 characters that are not the second character: 3
…
The nth character can be any of the 3 characters that are not the $(n-1)$th character: 3
$= 4 \cdot 3^{n-1} $