Results 1 to 4 of 4

Math Help - Three Part Recurrence Relation Problem

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    18

    Three Part Recurrence Relation Problem

    (a) Find a recurrence relation and initial conditions for b_{n}, the number of binary sequences of length n that do not contain 11.

    (b) Explain why the number of subsets of {1, 2, ..., n} that do not contain both i and i + 1 for i = 1, 2, ..., n-1 equals b_{n}. (Hint: appeal to a known 1-1 correspondence.)

    (c) Prove that b_{n} = f_{n+2}, where f_{n} is the n-th Fibonacci number, defined by f_{1} = f_{2} = 1, and f_{n} = f_{n-1} + f_{n-2} for n > 2. (One method that works is strong induction.)

    So far, this is what I have.

    (a)
    b_{n} = b_{n-1} + b_{n-2} for n \ge 2
    with b_{0} = 1 and b_{1} = 2

    (b)
    ???

    (c)
    I know
    f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, ...
    and that matches up with
    b_{1} = 2, b_{2} = 3, b_{3} = 5, ...
    So,
    f_{3} = b_{1}
    f_{4} = b_{2}
    f_{5} = b_{3}
    and so on, not sure what to do next.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello Celcius

    Welcome to Math Help Forum!
    Quote Originally Posted by Celcius View Post
    (a) Find a recurrence relation and initial conditions for b_{n}, the number of binary sequences of length n that do not contain 11.

    (b) Explain why the number of subsets of {1, 2, ..., n} that do not contain both i and i + 1 for i = 1, 2, ..., n-1 equals b_{n}. (Hint: appeal to a known 1-1 correspondence.)

    (c) Prove that b_{n} = f_{n+2}, where f_{n} is the n-th Fibonacci number, defined by f_{1} = f_{2} = 1, and f_{n} = f_{n-1} + f_{n-2} for n > 2. (One method that works is strong induction.)

    So far, this is what I have.

    (a)
    b_{n} = b_{n-1} + b_{n-2} for n \ge 2
    with b_{0} = 1 and b_{1} = 2
    Would you like to explain why?
    (b)
    ???
    The number of subsets is 2^n = the number of binary strings of length n. And we may set up a 1-1 correspondence between subsets and strings as follows:
    Choose any binary string of length n, say s_1s_2s_3...s_n.

    Create a subset of \{1, 2, 3, ..., n\} corresponding to this string by including in it the integer i if s_i=1 and excluding it if s_i=0.
    Thus the number of subsets that do not contain consecutive integers i and i+1 and the number of strings that do not contain the sequence 11 are therefore equal.
    (c)
    I know
    f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, ...
    and that matches up with
    b_{1} = 2, b_{2} = 3, b_{3} = 5, ...
    So,
    f_{3} = b_{1}
    f_{4} = b_{2}
    f_{5} = b_{3}
    and so on, not sure what to do next.
    If your answer to part (a) is correct, then this result follows immediately by induction.

    Assume that, for two consecutive integers k,\; k+1, b_k = f_{k+2} and b_{k+1} = f_{k+3}. Then, using the relation that defines a Fibonacci sequence,
    f_{k+4}= f_{k+3}+ f_{k+2}
    =b_{k+1}+b_k

    =b_{k+2}, using the answer to (a)
    Clearly b_0 = f_2 and b_1 = f_3 and that completes the proof.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    18
    Yes, for (a)
    I came up with those numbers first by counting a couple then creating the relation

    For b_0 you have 1 set, namely the empty set.
    For b_1 you have 2 sets, {0,1}.
    For b_2 you have 3 sets, {00, 01, 10}.
    For b_3 you have 5 sets, {000, 001, 010, 100, 101}.
    And so on. The way it becomes a recurrence was by, for example set b_3
    You first take b_2 = {00, 01, 10} and put a 0 in front of those sets, thus giving you {000, 001, 010}
    Then take b_1 = {0, 1} and put a 10 in front of those sets, thus giving you {100, 101}
    Which gives you the union of b_1, b_2 = b_3
    Therefore b_3 = {000, 001, 010, 100, 101}.
    And thus the recurrence is formed.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello Celcius
    Quote Originally Posted by Celcius View Post
    Yes, for (a)
    I came up with those numbers first by counting a couple then creating the relation

    For b_0 you have 1 set, namely the empty set.
    For b_1 you have 2 sets, {0,1}.
    For b_2 you have 3 sets, {00, 01, 10}.
    For b_3 you have 5 sets, {000, 001, 010, 100, 101}.
    And so on. The way it becomes a recurrence was by, for example set b_3
    You first take b_2 = {00, 01, 10} and put a 0 in front of those sets, thus giving you {000, 001, 010}
    Then take b_1 = {0, 1} and put a 10 in front of those sets, thus giving you {100, 101}
    Which gives you the union of b_1, b_2 = b_3
    Therefore b_3 = {000, 001, 010, 100, 101}.
    And thus the recurrence is formed.
    A more formal proof of this is as follows:

    Suppose we call a string that doesn't contain the string '11' a valid string. Then to every valid string of length (n-1) a zero may be added at the end to form a valid string of length n. Moreover, for every string of length n that ends in zero, the last character may be removed to form a valid string of length (n-1).

    Therefore the number of valid strings of length n that end in zero is exactly b_{n-1}.

    Similarly, the number of valid strings of length (n-1) that end in zero is b_{n-2}. Further for each of these strings, a '1' may be added to the end to form a valid string of length n.

    Therefore the number of valid strings of length n is b_{n-1}+b_{n-2}.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2011, 07:45 AM
  2. recurrence relation problem!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 9th 2011, 05:54 PM
  3. Writing up a Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 11th 2010, 06:55 PM
  4. Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 10th 2010, 03:41 PM
  5. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 11:23 AM

Search Tags


/mathhelpforum @mathhelpforum