[Discrete Math] Recurrence Relations

[Servo888]

Question:

"Find a recurrence relation and initial conditions for the sequence {a sub n} if a sub n is the number of bit strings of length n that contain three consecutive 0's."

So here's what I have so far...
n > 3
n = 4, 1000, 0001
n = 5, 10000, 00001, 00010, 01000, 10001
n = 6, 100000, 000001, 010000, 000010, 001000, 00100, 111000, 000111, 110001, 100011, 110000, 000011, 100001, 101000, 000101, 100010, 010001, ... I might have missed a few...

Anyways here's what I see... As n increases the number of bit strings increases (almost exponentially), and the maximum number of 1's in the string is n-3. In n-6, you have 3x1's.

That's all I have so far... And I don't know where else to go from here. So I would like some help with this.

 

[matt grime]

You have to get a recurrence relation. What is a recurrence relation?

 

[Servo888]

"...a recurrence relation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms."

 

[matt grime]

So how would you try to write the number of permissible strings of length n in terms of the lengths of smaller strings?

 

[Servo888]

I don't understand what you mean... But from what I gather if you have the string 100000, this can be written as string 100 + string 000 (concatination)

 

[matt grime]

You want to count the number of strings of length n. You need to figure out a way to relate this number to the number of strings of some smaller lengths. It's counting. (And it's concatenation.)

Ie you need to work out some relation with a_n and a_{n-1} and almost certainly some other a_{m}, that is what a recurrence relation is.. I'm not going to do this for you, nor should anyone else. You need to work through it. And I'm reluctant to say more because I'd like you to work out the method you need to use to count these things.

 

[Servo888]

My final answer is something along the lines of...

a_n = a_(n-1) + a_(n-2) + 2^(n-3)

Since you have 3 cases...
1 + a bit string of length n-1, the string has 3, 0's.
01 + a bit string of length n-2, the string has 3, 0's.
000 + a bit string of length n-3, and the string can be of any value since you have the 3, 0's.

 

[matt grime]

what happened to strings that start 001? but you certainly figured out the right method, well done.

 

[Servo888]

Good point!
Case 4:
001 + a bit string of length n-3, string has 3 0's.

So it's:
a_n = a_(n-1) + a_(n-2) + a_(n-3) + 2^(n-3)

 

[matt grime]

don't forget the initial conditions. or the three initial terms.