Solution: 2016 Fall Final - 10

Author: Michiel Smid

Question

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

Solution

Well, the first character can be $ {a, b, c, d, e} $: 5

The second character can be $ {a, b, c, d, e} - { \text{first character} } $: 4

The third character can be $ {a, b, c, d, e} - { \text{second character} } $: 4

…

The nth character can be $ {a, b, c, d, e} - { \text{previous character} } $: 4

$ 5 \cdot 4^{n-1} $