[Discrete Math] Recurrence Relations

In summary, a recurrence relation for the sequence {a sub n} where a sub n is the number of bit strings of length n that contain three consecutive 0's is a_n = a_(n-1) + a_(n-2) + a_(n-3) + 2^(n-3). The initial conditions are a_0 = 0, a_1 = 0, and a_2 = 0. The number of permissible strings increases as n increases, with a maximum of n-3 1's in the string. The method used to count these strings involves relating the number of strings of length n to the number of strings of smaller lengths.
  • #1
Servo888
43
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
  • #2
You have to get a recurrence relation. What is a recurrence relation?
 
  • #3
"...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
So how would you try to write the number of permissible strings of length n in terms of the lengths of smaller strings?
 
  • #5
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
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
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
what happened to strings that start 001? but you certainly figured out the right method, well done.
 
  • #9
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.
 

FAQ: [Discrete Math] Recurrence Relations

1. What is a recurrence relation in discrete math?

A recurrence relation is a mathematical equation that defines a sequence of numbers or values based on the previous terms in the sequence. It is often used to describe the behavior of a system over time.

2. How do you solve a recurrence relation?

To solve a recurrence relation, you can use various methods such as direct substitution, iteration, or the characteristic equation method. Depending on the complexity of the relation, you may need to use more advanced techniques such as generating functions or master theorem.

3. What is the difference between a linear and a nonlinear recurrence relation?

A linear recurrence relation is one in which the next term in the sequence is a linear combination of the previous terms. In contrast, a nonlinear recurrence relation involves nonlinear functions or terms in the equation. Linear recurrence relations are generally easier to solve compared to nonlinear ones.

4. How is a recurrence relation used in real-life applications?

Recurrence relations are used in various fields such as computer science, economics, and physics to model and analyze real-life situations. For example, they can be used to predict population growth, analyze the time complexity of algorithms, or model the behavior of physical systems.

5. Can a recurrence relation have more than one solution?

Yes, a recurrence relation can have multiple solutions. This is especially true for nonlinear recurrence relations, where there may be different initial conditions or different values for the parameters that can lead to different solutions. It is important to specify the initial conditions and parameters when solving a recurrence relation to determine the specific solution.

Similar threads

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

Hot Threads

Recent Insights

Back
Top