Developing Recurrence Formula (Closed)

[lovemake1]

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

 

[SammyS]

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

 

[Ray Vickson]

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

 

[lovemake1]

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.

 

[lovemake1]

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

 

[lovemake1]

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?