Question: 2019 Fall Midterm - 6

Author: Michiel Smid

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

(a)

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

(b)

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

(c)

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

(d)

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