Developing Recurrence Formula (Closed)

In summary, the problem is to find a recurrence formula for the function H(n), which counts the number of unique n-character strings composed of 0's and 1's, where each string must have an even number of 1's. The base cases are H(1) = 1, H(2) = 2, H(3) = 3, and H(4) = 5. The function H(n) is not defined for n < 0.
  • #1
lovemake1
149
1

Homework Statement



Given binary string of length n.
substrings of 1's should be even. (given 0 is a delimeter)
eg) 10111 is broken down into 1 and 111 (all odd)

so, for example string with H(n = 4)
0000 1100 0110 0011 1111
there are 5 of them.

H(n = 3)
000 110 011
there are 3 of them.

Q. Develop a recurrence for H(n), and show why it counts the number of strings correctly.

Homework Equations


The Attempt at a Solution



I have tried to form some kind of pattern but I am still not unable to form a recurrence.
we intuitively know that H(n=0) and H(n=1) are both 0 which is still even.
and H(n=2) = 2 since ( 00, 11) takes place.

I was thinking of setting basecase of recurrence upto n = 4.
so list

H(n)
2 n = 2
3 n = 3
5 n = 4
? n > 4

First of all, am I right to list basecases starting from 2?
and what are some crucial steps I need to take in order to find the right recurrence formula
Helps are much appreacited, thank you
 
Last edited:
Physics news on Phys.org
  • #2
lovemake1 said:

Homework Statement



I am given the following property of the strings.
each length n string must have even occurrence of 1's.

so, for example string with H(n = 4)
0000 1100 0110 0011 1111
there are 5 of them.

H(n = 3)
000 110 011
there are 3 of them.

Q. Develop a recurrence for H(n), and show why it counts the number of strings correctly.

Homework Equations



The Attempt at a Solution



I have tried to form some kind of pattern but I am still not unable to form a recurrence.
we intuitively know that H(n=0) and H(n=1) are both 0 which is still even.
and H(n=2) = 2 since ( 00, 11) takes place.

I was thinking of setting base case of recurrence up to n = 4.
so list

H(n)
2 n = 2
3 n = 3
5 n = 4
? n > 4

First of all, am I right to list base cases starting from 2?
and what are some crucial steps I need to take in order to find the right recurrence formula

Helps are much appreciated, thank you
First of all, your problem does not appear to be fully described. I had to read though it several times to figure out what you're supposed to accomplish here.

1. You (character) strings are composed entirely of 0's (zeros) and 1's (one's).

2. Each string has an even number of 1's in it.

3. The function, H(n), counts the number of unique n-character strings which can be composed in this manner.

From all this I gather that:
H(1) = 1
H(2) = 2
H(3) = 3
H(4) = 5
H(6) = 8   (I worked this one out.)​

How one defines H(0) depends upon a precise definition of what constitutes a string. If it makes sense to talk about a 0-character string, then H(0) = 1.

Do you see a pattern starting with H(3) ?

Once you see the pattern, it may be possible to see an easy way to construct the strings for the previous sets of strings. (Of course, that's somewhat the reverse order of what's often done.)
 
  • #3
lovemake1 said:

Homework Statement



I am given the following property of the strings.
each length n string must have even occurence of 1's.

so, for example string with H(n = 4)
0000 1100 0110 0011 1111
there are 5 of them.

H(n = 3)
000 110 011
there are 3 of them.

Q. Develop a recurrence for H(n), and show why it counts the number of strings correctly.

Homework Equations





The Attempt at a Solution



I have tried to form some kind of pattern but I am still not unable to form a recurrence.
we intuitively know that H(n=0) and H(n=1) are both 0 which is still even.
and H(n=2) = 2 since ( 00, 11) takes place.

I was thinking of setting basecase of recurrence upto n = 4.
so list

H(n)
2 n = 2
3 n = 3
5 n = 4
? n > 4

First of all, am I right to list basecases starting from 2?
and what are some crucial steps I need to take in order to find the right recurrence formula



Helps are much appreacited, thank you

Is there a reason you are not counting 1010, 0101 and 1001? These also have an even number of 1s.

RGV
 
  • #4
Ray Vickson said:
Is there a reason you are not counting 1010, 0101 and 1001? These also have an even number of 1s.

RGV

Sorry I worded poorly..
I should say that substrings of 1's should be even. (given 0 is a delimeter)
eg 10111 is broken down into 1 and 111 (all odd)
1011 is 1 and 11 (odd / even) but all has to be even so this is not right.
 
  • #5
SammyS said:
First of all, your problem does not appear to be fully described. I had to read though it several times to figure out what you're supposed to accomplish here.

1. You (character) strings are composed entirely of 0's (zeros) and 1's (one's).

2. Each string has an even number of 1's in it.

3. The function, H(n), counts the number of unique n-character strings which can be composed in this manner.

From all this I gather that:
H(1) = 1
H(2) = 2
H(3) = 3
H(4) = 5
H(6) = 8   (I worked this one out.)​

How one defines H(0) depends upon a precise definition of what constitutes a string. If it makes sense to talk about a 0-character string, then H(0) = 1.

Do you see a pattern starting with H(3) ?

Once you see the pattern, it may be possible to see an easy way to construct the strings for the previous sets of strings. (Of course, that's somewhat the reverse order of what's often done.)

Yea, I just realized that my H(5) was wrong because I accidently counted 11111, so the pattern here is H(n) = H(n-2) + H(n-1) for n >= 3 or (n > 2)

so this is just fibonnachi sequence, I'll work on getting the closed form of this and get back with what I have. Thank you
 
  • #6
so H(n) = H(n-1) + H(n-2)

1st substitution. H(n) = H(n-2) + H(n-3) + H(n-3) + H(n-4)
= H(n-2) + 2H(n-3) + H(n-4)

2nd substitution. = [H(n-3) + H(n-4)] + 2[H(n-4) + H(n-5)] + [H(n-5) + H(n-6)]
= H(n-3) + 3H(n-4) + 3H(n-5) + H(n-6)

3rd substitution = H(n-4) + H(n-5) + 3[H(n-5) + H(n-6)] + 3[H(n-6) + H(n-7)] + [H(n-7) + H(n-8)]
= H(n-4) + 4H(n-5) + 6H(n-6) + 4H(n-7) + H(n-8)

4th Substitution = H(n-5) + H(n-6) + 4[H(n-6) + H(n-7)] + 6[H(n-7) + H(n-8)] + 4[H(n-8) + H(n-9)] + H(n-9) + H(n-10)
= H(n-5) + 5H(n-6) + 10H(n-7) + 10H(n-8) + 5H(n-9) + H(n-10)Heres my shot at forming a closed form.
H(n-k) + kH(n-k-1) + H(n-k/2) + summation( the middle term)
first term, second term, and last term + middle terms

I am unsure of what this will look like for the middle term because they are constantly increasing in size...

My course note has golden ratio but I am not sure why our prof is making us use repeated substitution.
is it possible to conclude golden ratio by using repeated substitution?
 
Last edited:

1. What is a recurrence formula (closed form)?

A recurrence formula, also known as a closed form, is a mathematical equation used to express a sequence of numbers or values in terms of the previous values in the sequence. It allows for a more efficient and concise representation of the sequence compared to listing out all the values individually.

2. What are the benefits of using a recurrence formula?

Using a recurrence formula can save time and effort in calculating values in a sequence, as well as provide a better understanding of the pattern or relationship between the values. It can also allow for easier manipulation and analysis of the sequence.

3. How do you develop a recurrence formula?

To develop a recurrence formula, you first need to identify the pattern or relationship between the values in the sequence. This can be done by carefully observing the sequence and looking for common differences or ratios between the values. Once the pattern is identified, it can be expressed in terms of the previous values using mathematical operations and symbols.

4. Can all sequences be expressed using a recurrence formula?

No, not all sequences can be expressed using a recurrence formula. Some sequences may have a more complex pattern or may not have a clear relationship between the values, making it difficult to develop a closed form. In these cases, other methods such as recursive formulas or direct computation may be used.

5. How do you know if a recurrence formula is correct?

To determine if a recurrence formula is correct, you can use it to calculate several values in the sequence and compare them to the actual values. If the calculated values match the actual values, then the recurrence formula is likely correct. Additionally, you can also use mathematical induction to prove the correctness of a recurrence formula.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
32
Views
6K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top