2. Let anthe number of bit strings of length n that do not have three consecutive 1's a) Find as by listing all the bit strings of length 3 that do not have three consecutive 1's b) Explain why an bn on + dn if bnthe number of bit strings if ba of length n that do not have three consecutive 1's a 0 and Cn = the number of bit strings of length n that do not have three consecutive 1's and end in 01 and dn-the number of bit strings of length n that do not have three consecutive 1's and end in 11. c) Explain why ba an-1 and Cn-an-2 and dn an-3 d) Find a recurrence relation for an. for n With