IMC 2020 · Problem 1

Let $n$ be a positive integer. Compute the number of words $w$ (finite sequences of letters) that satisfy all the following three properties:

(1) $w$ consists of $n$ letters, all of them are from the alphabet $\{\mathsf{a}, \mathsf{b}, \mathsf{c}, \mathsf{d}\}$;

(2) $w$ contains an even number of letters $\mathsf{a}$;

(3) $w$ contains an even number of letters $\mathsf{b}$.

(For example, for $n = 2$ there are 6 such words: $\mathsf{aa}$, $\mathsf{bb}$, $\mathsf{cc}$, $\mathsf{dd}$, $\mathsf{cd}$ and $\mathsf{dc}$.)