[Discrete Math] Recurrence Relations

Click For Summary

Homework Help Overview

The discussion revolves around finding a recurrence relation and initial conditions for the sequence {a sub n}, which represents the number of bit strings of length n containing three consecutive 0's. Participants explore the properties of such strings and the implications of their lengths.

Discussion Character

  • Exploratory, Mathematical reasoning, Problem interpretation

Approaches and Questions Raised

  • Participants discuss how to express the number of permissible strings of length n in terms of smaller strings. There are attempts to identify patterns in the sequences and to formulate a recurrence relation based on these observations.

Discussion Status

Some participants have proposed a potential recurrence relation and are refining their understanding of how to account for different cases of bit strings. There is acknowledgment of the need for initial conditions and further clarification on specific cases, indicating a productive exploration of the problem.

Contextual Notes

Participants note the importance of considering various cases for the strings, including those that begin with specific patterns. The discussion reflects a collaborative effort to clarify definitions and assumptions related to recurrence relations.

Servo888
Messages
43
Reaction score
0
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.
 
Physics news on Phys.org
You have to get a recurrence relation. What is a recurrence relation?
 
"...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."
 
So how would you try to write the number of permissible strings of length n in terms of the lengths of smaller strings?
 
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)
 
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.
 
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.
 
what happened to strings that start 001? but you certainly figured out the right method, well done.
 
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
don't forget the initial conditions. or the three initial terms.
 

Similar threads

Where Does 10^{n-1} Come From in the Recurrence Relation Example?
  • · Replies 6 ·
Replies
6
Views
4K