1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Please help understand the solution on Math Induction

  1. Aug 29, 2010 #1
    1. The problem statement, all variables and given/known data

    Please help me understand the given solution. Is there a simpler way of solving the problem?

    2. Relevant equations



    3. The attempt at a solution
     

    Attached Files:

    • pic.jpg
      pic.jpg
      File size:
      48.2 KB
      Views:
      127
  2. jcsd
  3. Aug 29, 2010 #2
    I am no expert but this is usually the proof given in most txtbooks.
    The proof is board, so which part do you not understand ?

    Do you know the definition of the power set ? Can you follow the logic of the proof or are you having trouble with the logic ?

    Please, elaborate on your difficulties.
     
    Last edited: Aug 29, 2010
  4. Aug 29, 2010 #3
    I don't follow logic....
     
  5. Aug 29, 2010 #4
    I don't blame you. The author has a not so friendly way of proving his proposition.

    Basically, what the author is trying to do is use induction to show the if a set, A, has n elements then p(A) has 2^n elements. This much I know you understand.

    The logic

    The author shows that for n=0 this holds
    The author uses the inductive hypothesis and assumes it holds for some K then, he tries to show it holds for K+1. This much I believe you understand.

    To accomplish his purpose the author does the following. He takes a set of K+1 elements. Lets call this set A.
    He then defines a set B like this
    B= A/{x} [ B has all the elements in A except x ( some x ) , therefore B has K elements ]

    We know by inductive hypothesis p(B) has 2^k elements, since B has K elements.

    We also know that if we take every subset of A it is either a subset of B or a set that contains the element x. Now we know there are two possible cases.

    Cases
    1) We have a subset of A that contains x
    2) We have a subset of A that does not contain x.

    We know that all subsets of B lie in A. We also know that the only thing that B is lacking is the element x.

    So from this we can "conclude" , based on the two cases, that for every subset of A there are two kinds; one that contains x and one that does not. p(B) is a collection of all subsets of A that do not have x . So this means there is a p(B*) which consist of every subset of A that contains x.

    Considering there are only two cases we can match up all the subsets that contain x and those that do not contain x.

    That is, we can form a bijection from p(B) to p(B*).

    From this we see that p(A) = 2p(B) = 2*2^k = 2^(k+1)


    Do you understand a little more ?
     
    Last edited: Aug 29, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook