Question: 2016 Fall Midterm - 6

Author: Michiel Smid

Let $n \geq 5$ and consider strings of length $n$ consisting of the characters $a$, $b$, $c$, and $d$. How many such strings are there that start with $ad$ or end with $dcb$?

(a)

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

(b)

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

(c)

$4^n - 4^{n - 5}$

(d)

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