# [Discrete Math] Recurrence Relations

1. Apr 16, 2006

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

2. Apr 16, 2006

### matt grime

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

3. Apr 16, 2006

### 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."

4. Apr 16, 2006

### 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?

5. Apr 16, 2006

### 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)

6. Apr 16, 2006

### 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 becuase I'd like you to work out the method you need to use to count these things.

7. Apr 16, 2006

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

8. Apr 16, 2006

### matt grime

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

9. Apr 16, 2006

### 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)

10. Apr 16, 2006

### matt grime

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