Register to reply 
Proof: Number of different subsets of A is equal to 2^n? 
Share this thread: 
#1
Sep1212, 10:49 PM

P: 218

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 2^{n}. 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 2^{n} 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)=2^{n} 


#2
Sep1212, 11:03 PM

HW Helper
Thanks
PF Gold
P: 7,632




#3
Sep1312, 09:13 AM

P: 218

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.



#4
Sep1312, 11:29 AM

HW Helper
Thanks
PF Gold
P: 7,632

Proof: Number of different subsets of A is equal to 2^n?
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?



#5
Sep1312, 05:46 PM

P: 218

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
Sep1312, 11:11 PM

P: 218

So, 2*2^k=2^(k+1), is that right?



#8
Sep1412, 11:32 AM

HW Helper
Thanks
PF Gold
P: 7,632




#9
Sep1512, 10:51 AM

P: 218

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



Register to reply 
Related Discussions  
Subsets of a set such that no two have two equal elements  Calculus & Beyond Homework  0  
Number of even/odd subsets.  Set Theory, Logic, Probability, Statistics  2  
The intersection of an empty collection of subsets of X is equal to X?  Set Theory, Logic, Probability, Statistics  2  
Proof that 1/2 +2/3 + 3/4...does not equal a whole number  Linear & Abstract Algebra  22  
The Number Of Proper Subsets is 2^n  1  Introductory Physics Homework  9 