Results 1 to 3 of 3

Math Help - The valid subsets and reccurence relation

  1. #1
    Junior Member
    Joined
    Mar 2008
    Posts
    56

    The valid subsets and reccurence relation

    Hi all.
    I'm struggling with the one quite hard question for me:

    Let I_n = {1,2,3,...,n} for n belong to N. A valid subset of I_n does not contain two numbers of the form x, x+1 for 1<=x<n. For example, {1,3,5} is valid but {1,3,4} is invalid. Let a_n denote the number of valid subsets of I_n.

    How can i list explicitly the valid subsets of I_k for k<=4 ?
    and how can i derive a recurrence relation for a_n (how can i obtain the formula)?

    For any advice I'll be very appreciate

    Regards
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    k=0:
    The empty set matches the criteria, so I_0 = 1

    k=1:
    \phi , \left\{1\right\}
    So I_1=2

    k=2:
    \phi , \left\{1\right\},\left\{2\right\}
    So I_2=3

    k=3:
    \phi , \left\{1\right\},\left\{2\right\}, \left\{3\right\}, \left\{1,3\right\}
    So I_3=5

    k=4:
    \phi , \left\{1\right\},\left\{2\right\}, \left\{3\right\}, \left\{4\right\}, \left\{1,3\right\}, \left\{1,4\right\}, \left\{2,4\right\}
    So I_4=8

    So we want to find a recurrence relation for I_n. We can observe that given I_{n-1}, I_n = I_{n-1} + P(n)
    Where P(n) is the number of valid subsets that do not contain (n-1).
    But it is easily seen that P(n) = I_{n-2}, and so we get:

    I_n = I_{n-1} + I_{n-2} , as expected.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,643
    Thanks
    1594
    Awards
    1
    Quote Originally Posted by Snowboarder View Post
    Let I_n = {1,2,3,...,n} for n belong to N. A valid subset of I_n does not contain two numbers of the form x, x+1 for 1<=x<n. For example, {1,3,5} is valid but {1,3,4} is invalid. Let a_n denote the number of valid subsets of I_n.
    Here is a way to see how the recursion works.
    Let’s say n\ge 3. Any subset valid in I_{n-1} would of course be valid in I_{n}.
    Now subsets in I_{n-2} do not contain the number {n-1}.
    So if we form these unions, J = \left\{ {\{ n\}  \cup Y:Y \in I_{n - 2}  \wedge Y} \text{ is valid}\right\} , that is we put {n} into every valid set in I_{n-2}.
    So now we have  a_{n}= a_{n-1}+a_{n-2}.
    Last edited by Plato; August 25th 2009 at 08:06 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sigma reccurence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 13th 2010, 04:49 AM
  2. Solve a reccurence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2009, 11:59 PM
  3. Reccurence relation
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 1st 2009, 01:43 AM
  4. valid,non valid arguments
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 8th 2009, 06:12 PM
  5. reccurence relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 28th 2009, 06:13 AM

Search Tags


/mathhelpforum @mathhelpforum