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$?
Answer: $E_n = 2E_{n-1} + O_{n-1}$
Attempt:
I was confused by this question. I took $n=2$. In this case for $E_n$, there is only $1$ way to have $2$ c’s.
For $n=3$, $E_n$ has $3$ possible strings that have $2$ c’s.
And for $O_n$, $n=2$, there is again only $2$ ways to have odd number of c’s.
For $n=3$, $E_3 = 2E_2 + O_2 = 2 \cdot 2+2 = 6$, which is not equal to $3$.
Best Answer
To get a string of length $n$ with an even number of $c$'s you can either start with a string of length $n-1$ that has an even number and add either an $a$ or a $b$, which gives the term $2E_{n-1}$ or start with a string of length $n-1$ that has an odd number of $c$'s and add a $c$, giving $O_{n-1}$. $O_2=4$ because there are $ac,bc,ca,cb$. $E_2=5$ because there are $aa,ab,ba,bb,cc$.