The recurrence relation for the number of bit strings of length n that contain a pair of consecutive 0's,a_n=a_n-1+a_n+2+2^n-2 with initial condition a0=0,a1=0 . determine the number of bit strings of length 20.
Answers
Step-by-step explanation:
Let's examine admissible strings of length 4. They are the eight strings
0000,0001,0010,0100,1000,0011,1001,1100
Notice that since the admissible strings of length 3 are
000,001,100
you counted the six strings
0000,0001,0010,0011,1000,1001
in your 2a3 admissible strings of length 4 that can be formed by appending a 0 or 1 to the end of an admissible string of length 3.
Since the inadmissible strings of length 2 are
01,10,11
you counted the three strings
0100,1000,1100
among the 2n−2−an−2 among the admissible strings of length 4 that can be formed by appending 00 to an inadmissible string of length 2.
Notice that you have counted the string 1000 twice since 100 is an admissible string of length 3 and 10 is an inadmissible string of length 2. The problem, as stated above, is that 10 is an inadmissible string of length 2 that can be extended to an admissible string of length 3 by appending a 0 to the end of an inadmissible string of length 2 that ends in a zero.