Recursive sequence question?

Question

Describe each sequence recursively. Include initial conditions and assume that the sequences begin with a(1).

a(n) = the number of bit strings of length n with an even number of 0s

Answer 1

Obviously a(1) = 1.
A digit string of length n will have an even number of 0s if and only if either:
- the last digit is 0 and the previous (n-1) digits contained an odd number of 0s, or
- the last digit is 1 and the previous (n-1) digits contained an even number of 0s.
We also know that there are 2^(n-1) bit strings of length n-1; a(n-1) of them have an even number of 0s and 2^(n-1) - a(n-1) of them have an odd number of 0s.
So we get
a(n) = 2^(n-1) - a(n-1) + a(n-1) = 2^(n-1).

This kind of obviates the need for a recursive formula, but you could use a(n) = 2a(n-1). I think that's probably harder to derive though. (I think you'll have to prove that there are as many odd as even for a given length, which is the same as proving a(n) = 2^(n-1).)

Answer 2

Well, let's start with bit strings of length 1 just to get a feel for this. There are two strings: 0 and 1. One of them has an even number of 0s. It's the 1 string, which has zero 0s, zero being an even number.

More generally:

It becomes clear that the last digit decides whether the number of 0s is even or odd. So, given all the strings of length n, exactly half of them have an even number of 0s.

As for how many strings of length n there are: each digit has two choices, either 0 or 1. So, the total number of strings of length n has to be 2^n.


Summarizing the results, if a(n) is the total number of strings of length n, then a(n) = 2^n/2 = 2^(n-1), i.e. the sequence goes 1, 2, 4, 8, 16, etc.