Solution: 2017 Winter Midterm - 6

Author: Michiel Smid

Question

Let

n \geq 4

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

a b

or start with

a b c

(a)

4^{n - 3}

(b)

4^{n}

(c)

4^{n - 1}

(d)

4^{n - 2}

We can break this down into 2 cases:

A = strings that start with $a b$

There is $1$ way to arrange the first 2 bits and $4^{n - 2}$ ways to choose the last $n - 2$ bits: $1 \cdot 4^{n - 2}$

B = strings that start with $a b c$

There is $1$ way to arrange the first 3 bits and $4^{n - 3}$ ways to choose the last $n - 3$ bits: $1 \cdot 4^{n - 3}$

$A \cap B =$ strings that start with $a b$ and start with $a b c$

There is $1$ way to arrange the first 3 bits and $4^{n - 3}$ ways to choose the last $n - 3$ bits: $1 \cdot 4^{n - 3}$

$| A \cup B | = | A | + | B | - | A \cap B |$

$| A \cup B | = 1 \cdot 4^{n - 2} + 1 \cdot 4^{n - 3} - 1 \cdot 4^{n - 3}$

$| A \cup B | = 4^{n - 2} + 4^{n - 3} - 4^{n - 3}$

$| A \cup B | = 4^{n - 2}$