Finding Recurrence Relation for Bit Strings with Consecutive Zeros

In summary, the conversation discusses a recurrence equation for bit strings of length n and the number of consecutive 0s in each string. The equation is represented as An = 2(an-1) + 3(an-2) + 2n-2, with three cases: starting with 0, starting with 1, and starting with 0 0. The conversation also mentions overlaps between cases, but it is simpler to consider three mutually exclusive cases.
  • #1
Miike012
1,009
0
I am having difficulty knowing which "cases" include in the recurrence equation.

My solution to problem in paint document.

Cases 1 - 6:
All cases contain strings of length n
Let ak represent number of bit string of length k with a pair of consecutive 0s.

For cases 1 and 2.
an-1, k = n-1.

1. Start with 0
0_ _ ... _
2. Start with 1
1_ _ ... _

For cases 3 - 5
an-2, k = n-2.

3. Start with 1 0
1 0 _ ... _
4. Start with 1 1
1 1 _ ... _
5. Start with 0 1
0 1 _ ... _

Case 6
an-2 = 2n-2

6. Start with 0 0
0 0 _ ... _

Therefore
An = (sum of ak from case 1 and 2) + (sum of ak from case 3,4, and 5) + (ak from case 6) =
2(an-1) + 3(an-2) + 2n-2

Cases that "overlap"
1 and 5: if second term of case 1 is 1
1 and 6: if second term of case 1 is 0

2 and 3: if second term of case 2 is 0
2 and 4: if second term of case 2 is 1

Therefore
an = 2(an-1) - (an-2) + 2n-2 = An - 4(an-2)
 

Attachments

  • QQQQ.jpg
    QQQQ.jpg
    4.6 KB · Views: 404
Last edited:
Physics news on Phys.org
  • #2
I couldn't follow how you got your final equation from the various cases.
But it's much simpler if you just consider three mutually exclusive cases instead of having to subtract out overlaps. What are the three cases?
 

Related to Finding Recurrence Relation for Bit Strings with Consecutive Zeros

1. What is a recurrence relation?

A recurrence relation is a mathematical equation that defines a sequence of numbers based on the previous terms in the sequence. It is used to describe a pattern or relationship between the terms in a sequence.

2. Why is finding a recurrence relation important?

Finding a recurrence relation is important because it allows us to predict and understand the behavior of a sequence of numbers. It also helps us to efficiently calculate large values in the sequence without having to manually compute each term.

3. What are some strategies for finding a recurrence relation?

Some strategies for finding a recurrence relation include looking for patterns in the sequence, using known mathematical formulas and identities, and breaking down the problem into smaller subproblems.

4. Can a recurrence relation be solved in closed form?

Yes, some recurrence relations can be solved in closed form, meaning that the value of any term in the sequence can be directly calculated without having to compute the previous terms. However, not all recurrence relations have closed form solutions.

5. How is a recurrence relation different from a recursive function?

A recurrence relation is a mathematical equation that describes the relationship between terms in a sequence, while a recursive function is a programming concept that involves a function calling itself until a base case is reached. A recurrence relation can be used to create a recursive function, but they are not the same thing.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
11
Views
195
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
Replies
12
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
16
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
950
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
662
Back
Top