Results 1 to 3 of 3

Thread: 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
    $\displaystyle k=0:$
    The empty set matches the criteria, so $\displaystyle I_0 = 1$

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

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

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

    $\displaystyle k=4:$
    $\displaystyle \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 $\displaystyle I_4=8$

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

    $\displaystyle 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
    21,796
    Thanks
    2827
    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 $\displaystyle n\ge 3$. Any subset valid in $\displaystyle I_{n-1}$ would of course be valid in $\displaystyle I_{n}$.
    Now subsets in $\displaystyle I_{n-2}$ do not contain the number $\displaystyle {n-1}$.
    So if we form these unions, $\displaystyle J = \left\{ {\{ n\} \cup Y:Y \in I_{n - 2} \wedge Y} \text{ is valid}\right\}$ , that is we put $\displaystyle {n}$ into every valid set in $\displaystyle I_{n-2}$.
    So now we have $\displaystyle a_{n}= a_{n-1}+a_{n-2}$.
    Last edited by Plato; Aug 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: Oct 13th 2010, 04:49 AM
  2. Solve a reccurence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 15th 2009, 11:59 PM
  3. Reccurence relation
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Nov 1st 2009, 01:43 AM
  4. valid,non valid arguments
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Sep 8th 2009, 06:12 PM
  5. reccurence relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Jan 28th 2009, 06:13 AM

Search Tags


/mathhelpforum @mathhelpforum