Use the following steps to define a recurrence relationship for the number of bit sequences of length n with an even number of 0s.

a) Give a recurrence relation and justify each term, for bit strings of length n>=0. Note that a bit string with no 0s has an even number of 0s.

b) What are the initial conditions?

c) List the bit strings of length 5 that have an even number of 0s using the justification you gave for each term in your recurrence.