Thread: Discrete math

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

Originally Posted by skii

Let an be the number of bit strings of length n that contain the string 00 (two consecutive zeroes).
(a) Find a1, a2, a3, a4
(b)Find a recurrence relation for the sequence

Originally Posted by tester85

Please
Let an be the number of ternary strings of length n containing two consecutive 0s.

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!

Thread updated. Thanks for pointing out the mistake. I hope it is correct now

Originally Posted by skii

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.

Well obviously a_1=0, a_2=1.

a_3=2, as the none zero bit bay be the first or last

a_4= , well I will leave that to you, just list them and count.

CB