Find a recurrence relation for the number of decimal strings

Find a recurrence relation for the number of decimal strings of length n that contain a pair of consecutive zeros.

Solution

let an denote the number of bit strings of length n that contain pair of consecutive zeros

If a string of length n ends

with 1 and contains a pair of consecutive 0s, then such a pair should

be somewhere inside of the first n 1 positions, so that we have

an-1 such strings

If a string of length n ends with 10 and contains a pair of

consecutive 0s, then such a pair should be somewhere inside of the first

n 2 positions, so that we have an-2 such strings

If a string of length

n ends with 00, then, whatever bits are at the first n 2 positions,

such a string already contains a pair of consecutive 0s, and we have

2^(n-2) such strings

=>

recurrence relation is an = an-1 + an-2 + 2^(n-2)