find a recurrence relation...

• October 27th 2008, 03:12 AM
Narek
find 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, 07:01 AM
Narek
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, 08:08 AM
Plato
Quote:

Originally Posted by Narek
here is the solution:
a(n) = 2^n - 2^n
a(n) = a(n-1) - a(n-2)

Of course it is not true. Did you just makeup that answer?
Do you realize that zero is an even number?
So $a_1 =1$; the bit-string “1” contains an even number of zeros.
And $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 $a_9 = \sum\limits_{k = 0}^4 {9 \choose {2k}} = 256$.
In general $a_n = \sum\limits_{k = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {n \choose {2k}} = 2^{n - 1}$