1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Developing Recurrence Formula (Closed)

  1. Oct 31, 2012 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

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

    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: Oct 31, 2012
  2. jcsd
  3. Oct 31, 2012 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.)
  4. Oct 31, 2012 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

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

  5. Oct 31, 2012 #4
    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.
  6. Oct 31, 2012 #5
    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
  7. Oct 31, 2012 #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: Oct 31, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook