Let an be the number of bit strings of length n (n = 1, 2, ...) that contain the string 00 (two consecutive zeroes).
(a) Find a1, a2, a3, a4.
(b) Find a recurrence relation for the sequence {an}.
Please take note an should be a subscript n
Please take note an should be a subscript n
Let an be the number of bit strings of length n containing two consecutive 0s. These an strings consist of:
the strings starting with 1 --- the number is an-1
the strings starting with 01 --the number is an-2
the strings starting with 00 --the number is 3n−2
Therefore, the recurrence relation is:
an = an−1 + an−2 + 3n−2 , for n ≥ 3
Initial conditions: a1 = 0, a2 =1
a3 = a2 + a1 + 31 = 1 + 0 + 3 = 4
a4 = a3 + a2 + 32 = 4 + 1 + 9 = 14
Why were bit strings changed to ternary strings?
The OP is clearly about bit strings.
Moreover, I wonder if the word not was left out of the OP?
“the number of bit strings of length n that do not contain the string 00”?
That is a very nice recurrence relation! As stated it is not!