find a recurrence relation for the number of bit sequences of length n with an even number of 0s (Rofl)

Thank you so much (Itwasntme)

Printable View

- October 27th 2008, 04:12 AMNarekfind a recurrence relation...
find a recurrence relation for the number of bit sequences of length n with an even number of 0s (Rofl)

Thank you so much (Itwasntme) - October 27th 2008, 08:01 AMNarek
*here is the solution:*

*a(n) = 2^n - 2^n*

*a(n) = a(n-1) - a(n-2)*

*is it true? (Nerd)* - October 27th 2008, 09:08 AMPlato
**Of course it is not true.**Did you just makeup that answer?

Do you realize that zero is an even number?

So ; the bit-string “1” contains an even number of zeros.

And ; 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 .

In general