Answer to Question #329160 in Discrete Mathematics for Samuel

Question

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

Answer 1

Let $f(n)$ - number of bit sequences of length n with an odd number of 0's.

Total number of bit sequences of length n is $2^n$ (we can choose each bit by 2 ways - 0 or 1, total number of combinations is equal to the production of numbers of ways of choosing each bit, which is $2^n$)

We can construct bit sequence of length n by appending to each of bit sequences of length n - 1 a single bit 0 or 1. When appending 1, amount of 0's remains the same, so among this type of sequences (which are ending with 1) number of those with an odd number of 0's is equal to $f(n-1)$. Appending 0 changes resulting number of 0's from even to odd and from odd to even, so number of those with an odd number of 0's is equal to (number of sequences of length n - 1 with an even number of 0's) = (total number of sequences of length n - 1 minus number of sequences of length n - 1 with an odd number of 0's) = $2^{n-1}-f(n-1)$

We should add numbers of sequences with an odd number of 0's among those ending with 1 and ending with 0:

$f(n)=f(n-1)+(2^{n-1}-f(n-1))=2^{n-1}$ ,

so number of these sequences does not depend directly on the number of this type of sequences with lower length.