Counting Strings: Consider strings consisting of characters, where each character is one of the letters a, b, and c.

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

• Remember that 0 is even, so the strings which have 0 c's should be counted in $E_n$ as well. Also note that you can use different letters. $E_2$ should be 9, as there is one string with 2 c's, and 8 strings with 0 c's. – platty Nov 29 '18 at 23:59
• @platty: there are only $4$ strings of two letters with no $c$s, so $E_2$ should be $5$ – Ross Millikan Nov 30 '18 at 0:06
• Yes, my bad (I was thinking $E_3$). – platty Nov 30 '18 at 0:06

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