Results 1 to 2 of 2

Math Help - strong induction problem involving power set

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    strong induction problem involving power set

    hi

    Here is a problem I am trying to do.

    For each positive integer n, let

    A_n=\{1,2,\cdots,n\}

    and

    P_n=\{X\in \mathcal{P}(A_n)\lvert \;\mbox{X does not contain two consecutive integers }\;\}

    For example,

    P_3=\{\varnothing,\{1\},\{2\},\{3\},\{1,3\}\}

    Prove that for every n, the number of elements in P_n is
    F_{n+2}, the (n+2)^{\mbox{th}} Fibonacci number.

    for example , the number of elements in P_3 is 5=F_5.

    there is one hint given in the problem...
    Hint: Which elements of P_n contain n ? Which don't ?
    The answers to both questions are related to the elements of P_m
    for certain m<n ....

    now I see that elements of P_{n-1} does not contain n.

    So let me put the goal as

    \forall n\geqslant 1[P_n\;\mbox{has}\;F_{n+2}\;\mbox{elements}]

    Let

    Q(n)=[(n\geqslant 1)\Rightarrow(P_n\;\mbox{has}\;F_{n+2}\;\mbox{elem  ents})]

    so my goal now becomes ( for strong induction problem)

    \forall n[(\forall k<n Q(k))\Rightarrow Q(n)]

    So we let n be arbitrary and suppose that

    \forall k<n Q(k)\;\mbox{and}\; n\geqslant 1

    I start by proving base cases for n=1,2 . So consider the next case of
    n\geqslant 3

    Since

    1\leqslant (n-2)< n

    and

    1\leqslant (n-1)<n

    we can make use of the inductive hypothesis and conclude that

    P_{n-1}\;\mbox{has}\;F_{n+1}\;\mbox{elements}

    and

    P_{n-2}\;\mbox{has}\;F_{n}\;\mbox{elements}

    but after this point, I am stuck. Any hints ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: strong induction problem involving power set

    Quote Originally Posted by issacnewton View Post
    hi

    Here is a problem I am trying to do.

    For each positive integer n, let

    A_n=\{1,2,\cdots,n\}

    and

    P_n=\{X\in \mathcal{P}(A_n)\lvert \;\mbox{X does not contain two consecutive integers }\;\}
    P_{n+1}=P_n \cup  P^*_{n-1}

    Where P^*_{n-1}=\{ a \cup \{(n+1)\}; a\in P_{n-1} \}
    Last edited by CaptainBlack; October 8th 2011 at 09:58 PM. Reason: correct obvious typo
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] some problem in strong induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 6th 2011, 07:05 PM
  2. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  3. proof by induction question involving power set
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: January 22nd 2010, 08:18 AM
  4. Strong Induction Problem using Summations
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2009, 09:12 AM
  5. Strong Induction Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2008, 05:09 AM

/mathhelpforum @mathhelpforum