Results 1 to 4 of 4

Thread: 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 $\displaystyle b_{n}$, the number of binary sequences of length n that do not contain 11.

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

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

    So far, this is what I have.

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

    (b)
    ???

    (c)
    I know
    $\displaystyle f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, ...$
    and that matches up with
    $\displaystyle b_{1} = 2, b_{2} = 3, b_{3} = 5, ...$
    So,
    $\displaystyle f_{3} = b_{1}$
    $\displaystyle f_{4} = b_{2}$
    $\displaystyle 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 $\displaystyle b_{n}$, the number of binary sequences of length n that do not contain 11.

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

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

    So far, this is what I have.

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

    Create a subset of $\displaystyle \{1, 2, 3, ..., n\}$ corresponding to this string by including in it the integer $\displaystyle i$ if $\displaystyle s_i=1$ and excluding it if $\displaystyle s_i=0$.
    Thus the number of subsets that do not contain consecutive integers $\displaystyle i$ and $\displaystyle i+1$ and the number of strings that do not contain the sequence $\displaystyle 11$ are therefore equal.
    (c)
    I know
    $\displaystyle f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, ...$
    and that matches up with
    $\displaystyle b_{1} = 2, b_{2} = 3, b_{3} = 5, ...$
    So,
    $\displaystyle f_{3} = b_{1}$
    $\displaystyle f_{4} = b_{2}$
    $\displaystyle 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 $\displaystyle k,\; k+1$, $\displaystyle b_k = f_{k+2}$ and $\displaystyle b_{k+1} = f_{k+3}$. Then, using the relation that defines a Fibonacci sequence,
    $\displaystyle f_{k+4}= f_{k+3}+ f_{k+2}$
    $\displaystyle =b_{k+1}+b_k$

    $\displaystyle =b_{k+2}$, using the answer to (a)
    Clearly $\displaystyle b_0 = f_2$ and $\displaystyle 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 $\displaystyle b_0$ you have 1 set, namely the empty set.
    For $\displaystyle b_1$ you have 2 sets, $\displaystyle {0,1}$.
    For $\displaystyle b_2$ you have 3 sets, $\displaystyle {00, 01, 10}$.
    For $\displaystyle b_3$ you have 5 sets, $\displaystyle {000, 001, 010, 100, 101}$.
    And so on. The way it becomes a recurrence was by, for example set $\displaystyle b_3$
    You first take $\displaystyle b_2 = {00, 01, 10}$ and put a 0 in front of those sets, thus giving you $\displaystyle {000, 001, 010}$
    Then take $\displaystyle b_1 = {0, 1}$ and put a 10 in front of those sets, thus giving you $\displaystyle {100, 101}$
    Which gives you the union of $\displaystyle b_1, b_2 = b_3$
    Therefore $\displaystyle 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 $\displaystyle b_0$ you have 1 set, namely the empty set.
    For $\displaystyle b_1$ you have 2 sets, $\displaystyle {0,1}$.
    For $\displaystyle b_2$ you have 3 sets, $\displaystyle {00, 01, 10}$.
    For $\displaystyle b_3$ you have 5 sets, $\displaystyle {000, 001, 010, 100, 101}$.
    And so on. The way it becomes a recurrence was by, for example set $\displaystyle b_3$
    You first take $\displaystyle b_2 = {00, 01, 10}$ and put a 0 in front of those sets, thus giving you $\displaystyle {000, 001, 010}$
    Then take $\displaystyle b_1 = {0, 1}$ and put a 10 in front of those sets, thus giving you $\displaystyle {100, 101}$
    Which gives you the union of $\displaystyle b_1, b_2 = b_3$
    Therefore $\displaystyle 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 $\displaystyle (n-1)$ a zero may be added at the end to form a valid string of length $\displaystyle n$. Moreover, for every string of length $\displaystyle n$ that ends in zero, the last character may be removed to form a valid string of length $\displaystyle (n-1)$.

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

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

    Therefore the number of valid strings of length $\displaystyle n$ is $\displaystyle 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: Nov 8th 2011, 06:45 AM
  2. recurrence relation problem!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 9th 2011, 04:54 PM
  3. Writing up a Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 11th 2010, 05:55 PM
  4. Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Oct 10th 2010, 02:41 PM
  5. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 11th 2008, 10:23 AM

Search Tags


/mathhelpforum @mathhelpforum