find a recurrence relation for the number of bit sequences of length n with an even number of 0s
Thank you so much
Of course it is not true. Did you just makeup that answer?
Do you realize that zero is an even number?
So $\displaystyle a_1 =1$; the bit-string “1” contains an even number of zeros.
And $\displaystyle a_2 =2$; the bit-strings “11” & “00” contain an even number of zeros.
Now suppose we think about bit-strings of length 9.
The 9-bit-strings we want to count contain 0,2,4,6,or 8 zeros.
We have nine places to put the zeros because the other places will contain ones.
That is $\displaystyle a_9 = \sum\limits_{k = 0}^4 {9 \choose {2k}} = 256$.
In general $\displaystyle a_n = \sum\limits_{k = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {n \choose {2k}} = 2^{n - 1} $