Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof: Number of different subsets of A is equal to 2^n?

  1. Sep 12, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove that if a set a contains n elements, then the number of different subsets of A is equal to 2n.




    3. The attempt at a solution

    I know how to prove with just combinatorics, where to construct a subset, each element is either in the set or not, leading to 2n subsets. I want to know how to prove it with mathematical induction though. How would I start?

    I figured this using summation notation:
    [itex]\sum^{k=0}_{n}[/itex] (n k)=2n
     
  2. jcsd
  3. Sep 12, 2012 #2

    LCKurtz

    User Avatar
    Homework Helper
    Gold Member

    So the proposition you want to prove is that the number of subsets of a set with n elements is ##2^n##. Start with ##n=1## A set with a single element, call it ##S_1 = \{a\}## has two subsets: ##\{a\}, \Phi## which is ##2^1##. Now you need to prove the induction step: Assume a set with ##k## elements has ##2^k## subsets and use that to show a set with ##k+1## elements has ##2^{k+1}## subsets. That's how you start. It's easy and you don't need binomial coefficients to do it.
     
  4. Sep 13, 2012 #3
    Thank you. The part with k+1 elements is confusing me. I went through a long process of trying to make one side equal to the other, and it's not really working. :confused:
     
  5. Sep 13, 2012 #4

    LCKurtz

    User Avatar
    Homework Helper
    Gold Member

    If you start with a set with ##k## elements and ##2^k##subsets, and add another element, all the subsets of the original set are subsets of the larger set. What additional subsets are there?
     
  6. Sep 13, 2012 #5
    The additional subsets will be the ones formed using the new element? As if this new element is either in the subsets or not...
     
  7. Sep 13, 2012 #6

    LCKurtz

    User Avatar
    Homework Helper
    Gold Member

    Yes, so.....?
     
  8. Sep 13, 2012 #7
    So, 2*2^k=2^(k+1), is that right?
     
  9. Sep 14, 2012 #8

    LCKurtz

    User Avatar
    Homework Helper
    Gold Member

    Are you asking me if ##2\cdot 2^k = 2^{k+1}##? Of course, you know it does. Do you understand how to put this all together to make a well written induction proof of your theorem?
     
  10. Sep 15, 2012 #9
    Yes, thank you. I just thought I would have to go through the long, tedious process of proving both sides are equal using the summation formula. Thanks for all your help :approve:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Proof: Number of different subsets of A is equal to 2^n?
Loading...