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