Question

Find a recurrence relation for the number of bit sequences of length n with an even number of 0s.

Answer 1

Let a_n represent the number of bit sequences of length n with an evennumber of 0's

First case. The sequence starts with a 1, then the remaining sequence of length n-1 needs to contain an even number of 0's and there are a_n-1 such strings.

Second case. The sequence starts with a 0, then the remaining sequence of length n-1 needs to contain an odd number of 0's. There are 2^n-1 possible bit strings of which a_n have an even number of 0's, thus 2^n-1-a_n strings have an odd number of 0's.

a_n=a_n-1+2^n-1-a_n-1=2^n-1