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}.

Printable View

- October 20th 2008, 08:07 PMskiiDiscrete 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}. - October 21st 2008, 05:42 AMtester85
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 - October 21st 2008, 09:52 AMPlato
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! - October 21st 2008, 05:29 PMtester85
Thread updated. Thanks for pointing out the mistake. I hope it is correct now (Wink)

- October 22nd 2008, 01:56 AMCaptainBlack