here is the solution:
a(n) = 2^n - 2^n
a(n) = a(n-1) - a(n-2)
is it true?
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 .