A bit string is called legitimate if it contains no consecutive zeros, e.g., 0101110 is legitimate, whereas 10100111 is not. Let an denote
the number of legitimate bit strings of length n. Dene a0 = 1. Derive a recurrence relation for an (i.e., express an in terms of the preceding ai's).