Question

How many bit sequences of length seven contain an even number of 0s?

Answer 1

Let $a_n$ denote the number of bit sequences of length n with an even number of 0's. There are two ways to form a valid string with n bits from a string with one fewer bit. First, a valid string of n digits can be obtained by appending a valid string of n – 1 bits with 1. Hence, a valid string with n bits can be formed in this manner in $a_{n-1}$ ways. Second, a valid string of n bits can be obtained by appending a 0 to a string length n – 1 that is not valid. The number of ways that this can be done equals the number of invalid (n – 1)-bit strings. Since there are 2^n-1 strings of length n – 1, and $a_{n-1}$  are valid, there are $2^{n-1} - a_{n-1}$  valid n-bit strings obtained by appending an invalid string of length n – 1 with a 0. Therefore

$a_n = a_{n-1} + (2^{n-1} – a_{n-1}) = 2^{n-1}$ for $n\geq2$ .

Hence, Recurrence relation is

$a_1=1 \\ a_n = 2 a_{n-1}$