Question: 2017 Fall Midterm - 6

Author: Michiel Smid

Let $n \geq 7$ be an integer and consider strings of length $n$ consisting of the characters $a$, $b$, $c$, and $d$. How many such strings are there that start with $abc$ or end with $dddd$?

(a)

$2 \cdot 4^{n-3} - 4^{n-7}$

(b)

$4^{n-3} + 4^{n-4} - 4^{n-7}$

(c)

$2 \cdot 4^{n-4} - 4^{n-7}$

(d)

$4^{n-3} + 4^{n-4}$