0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – platty Nov 29 '18 at 23:59
  • $\begingroup$ @platty: there are only $4$ strings of two letters with no $c$s, so $E_2$ should be $5$ $\endgroup$ – Ross Millikan Nov 30 '18 at 0:06
  • $\begingroup$ Yes, my bad (I was thinking $E_3$). $\endgroup$ – platty Nov 30 '18 at 0:06
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.