0
$\begingroup$

Q. How many strings in {0,1,2,3} have an even number of 1's.

The answer provided uses the recurrence relation $a_{n+1} = 3a_n + (4^n - a_n)$.

The hint given was that consider the last string of length $n+1$ is :
$0$ - Number of strings that can proceed is $a_n$.

I'm assuming that $a_n$ is the number of legal strings that can follow $0$.
So if there was a string $02123210$, since this string has an even number of ones ($a_n$), then $a_n$ strings can proceed the previous string.

Then it would be the same for $2,3$ resulting in the $3a_n$. I don't know however how the $(4^n-a_n)$ came about.

I've tried looking at What is the recurrence relation in this problem?. Since it looks similar to this problem.

$\endgroup$
2
$\begingroup$

Suppose $a_n$ is the number of GOOD strings of length $n$. By GOOD we mean the strings that satisfies the given criterion (i.e it has even number of $1's$). Then consider a GOOD string of length $n+1$. It can be made in two ways:

  1. Case 1: we start with a GOOD string of length $n$ and then add $0$ or $2$ or $3$ at the $n+1^{\text{st}}$ place. This way we have not changed the number of $1's$ that were already there in the string of length $n$.
  2. Case 2: we start with a BAD string of length $n$ (so it will have odd number of $1's$). Then we add a $1$ for the $n+1^{\text{st}}$ place. Thus converting it into a GOOD string of length $n+1$.

The number of strings from case 1 will be $3a_n$ (because of $3$ choices of ending a GOOD string of length $n$).

The number of strings from case 2 will be = the number of BAD strings of length $n$. This is same as total strings of length $n$ - the number of GOOD strings of length $n$.

The total number of strings of length $n$ made up of four symbols is $4^n$ and the number of GOOD strings of length $n$ is $a_n$. Therefore the total number of BAD strings of length $n$ is $4^n-a_n$.

I hope this helps.

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