Solution: 2017 Fall Final - 8

Author: Michiel Smid

Question

Consider strings consisting of characters, where each character is one of the letters $a$, $b$, and $c$.
For any integer $n \geq 1$, let $E_n$ be the number of such strings of length $n$ that contain an even number of $c$'s, and let $O_n$ be the number of such strings of length $n$ that contain an odd number of $c$'s. (Remember that 0 is an even number.)
Which of the following is true for any integer $n \geq 2$?

(a)

$E_n = 2 \cdot O_{n-1} + E_{n-1}$

(b)

$E_n = 2 \cdot O_{n-1} + O_{n-1}$

(c)

$E_n = 2 \cdot E_{n-1} + E_{n-1}$

(d)

$E_n = 2 \cdot E_{n-1} + O_{n-1}$

Solution

Well, let’s write out and see what happens. We start off with an even number of $c$‘s, which is 0

If we place an $a$, then we still have an even number of $c$‘s, so we call the even number of $c$‘s $E_{n-1}$

If we place a $b$, then we still have an even number of $c$‘s, so we call the even number of $c$‘s $E_{n-1}$

If we place a $c$, then we now have an odd number of $c$‘s, so we call the odd number of $c$‘s $O_{n-1}$

This means that $E_n = E_{n-1} + E_{n-1} + O_{n-1} = 2E_{n-1} + O_{n-1}$