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

  • Thread starter SMA_01
  • Start date
  • #1
SMA_01
218
0

Homework Statement



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




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
 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,568
774

Homework Statement



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




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

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.
 
  • #3
SMA_01
218
0
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:
 
  • #4
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,568
774
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
SMA_01
218
0
The additional subsets will be the ones formed using the new element? As if this new element is either in the subsets or not...
 
  • #6
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,568
774
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?

The additional subsets will be the ones formed using the new element? As if this new element is either in the subsets or not...

Yes, so.....?
 
  • #7
SMA_01
218
0
So, 2*2^k=2^(k+1), is that right?
 
  • #8
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,568
774
So, 2*2^k=2^(k+1), is that right?

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?
 
  • #9
SMA_01
218
0
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:
 

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

Replies
9
Views
525
Replies
7
Views
364
Replies
3
Views
206
Replies
4
Views
150
  • Last Post
Replies
1
Views
278
Replies
2
Views
507
Replies
2
Views
307
Top