[Math] Recurrence relation for of bit strings of length n

recurrence-relations

Find a recurrence relation for the number of bit strings
of length $n$ such that:

  1. number of all $0$s and $1$s is even.
  2. number of $0$s and number of $1$s is even.

Thank you.

Best Answer

(1) Let $a_n$ be the number of bit strings of length $n$ such that the total number of $0$’s and $1$’s is even. Clearly the total number of $0$’s and $1$’s is just the length of the bit string, and there are $2^n$ bit strings of length $n$, so

$$a_n=\begin{cases} 2^n,&\text{if }n\text{ is even}\\ 0,&\text{if }n\text{ is odd}\;. \end{cases}$$

This is a problem in which it’s actually easier to write down a closed form than a recurrence. If you must find a recurrence, you could note that $a_n=4a_{n-2}$ for all $n\ge 2$, with initial conditions $a_0=1$ and $a_1=0$.

(2) Let $b_n$ be the number of bit strings of length $n$ such that the number of $0$’s and the number of $1$’s in the string are both even. Clearly $b_n=0$ when $n$ is odd. Suppose that $n$ is even and positive. If $\sigma$ is an $n$-bit string, imagine removing the last two bits. If they are $01$ or $10$, the remaining $(n-2)$-bit string will have an odd number of $1$’s and an odd number of $0$’s. If they are $00$ or $11$, the the remaining $(n-2)$-bit string will have an even number of $1$’s and an odd number of $0$’s. In other words, each ‘good’ $n$-bit string is obtained either by appending $00$ or $11$ to a ‘good’ $(n-2)$-bit string or by appending $01$ or $10$ to a ‘bad’ $(n-2)$-bit string. From this you can calculate $b_n$ quite easily.

Related Question