Results 1 to 5 of 5

Math Help - induction proof help.

  1. #1
    Newbie
    Joined
    May 2013
    From
    Canada
    Posts
    11

    induction proof help.

    induction proof help.-qq-20130920165809.jpg
    I really stuck on the induction step , my TA suggest me to set cases for even quantity of P(n) and odd quantity of P(n) and start from there.induction proof help.-qq-20130920165828.jpg here is my work so far
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,923
    Thanks
    1762
    Awards
    1

    Re: induction proof help.

    Quote Originally Posted by hezhiweitian View Post
    Click image for larger version. 

Name:	QQ??20130920165809.jpg 
Views:	12 
Size:	24.2 KB 
ID:	29211
    I really stuck on the induction step , my TA suggest me to set cases for even quantity of P(n) and odd quantity of P(n) and start from there.
    Let S_n=\{1,2,\cdots,n\} then S_n contains \left\lfloor {\frac{{n}}{2}} \right\rfloor even numbers.

    Hence \math{P}(S_n) contains {2^{\left\lfloor {\frac{n}{2}} \right\rfloor }} sets with no odd numbers.
    Last edited by Plato; September 20th 2013 at 02:40 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2013
    From
    Canada
    Posts
    11

    Re: induction proof help.

    Quote Originally Posted by Plato View Post
    Let S_n=\{1,2,\cdots,n\} then S_n contains \left\lfloor {\frac{{n}}{2}} \right\rfloor even numbers.

    Hence \math{P}(S_n) contains {2^{\left\lfloor {\frac{n}{2}} \right\rfloor }} sets with no odd numbers.
    i understand the logical idea behind this , however I couldn't translate it into a formal induction proof .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,923
    Thanks
    1762
    Awards
    1

    Re: induction proof help.

    Quote Originally Posted by hezhiweitian View Post
    i understand the logical idea behind this , however I couldn't translate it into a formal induction proof .
    Oh, come on.
    Use induction to prove (S_n) contains {\left\lfloor {\frac{n}{2}} \right\rfloor }} even numbers.

    That is true for S_1: no even numbers.

    Suppose that (S_K) contains {\left\lfloor {\frac{K}{2}} \right\rfloor }} even numbers.

    Now (S_{K+1})=S_K\cup\{K+1\}. RIGHT?

    If K+1 is odd then (S_{K+1}) contains just as many even numbers as S_K. WHY?

    If K+1 is even then (S_{K+1}) contains one more even number than S_K.
    Note that if K+1 is even then \left\lfloor {\frac{{K + 1}}{2}} \right\rfloor  = \left\lfloor {\frac{K}{2}} \right\rfloor  + 1

    Can you finish?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2013
    From
    Canada
    Posts
    11

    Re: induction proof help.

    Quote Originally Posted by Plato View Post
    Oh, come on.
    Use induction to prove (S_n) contains {\left\lfloor {\frac{n}{2}} \right\rfloor }} even numbers.

    That is true for S_1: no even numbers.

    Suppose that (S_K) contains {\left\lfloor {\frac{K}{2}} \right\rfloor }} even numbers.

    Now (S_{K+1})=S_K\cup\{K+1\}. RIGHT?

    If K+1 is odd then (S_{K+1}) contains just as many even numbers as S_K. WHY?

    If K+1 is even then (S_{K+1}) contains one more even number than S_K.
    Note that if K+1 is even then \left\lfloor {\frac{{K + 1}}{2}} \right\rfloor  = \left\lfloor {\frac{K}{2}} \right\rfloor  + 1

    Can you finish?
    Thank you very much
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2011, 07:26 PM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  3. proof by induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 28th 2009, 09:11 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof by induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 5th 2006, 07:54 AM

Search Tags


/mathhelpforum @mathhelpforum