Register to reply

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

by SMA_01
Tags: equal, number, proof, subsets
Share this thread:
SMA_01
#1
Sep12-12, 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 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
Phys.Org News Partner Science news on Phys.org
Climate change increases risk of crop slowdown in next 20 years
Researcher part of team studying ways to better predict intensity of hurricanes
New molecule puts scientists a step closer to understanding hydrogen storage
LCKurtz
#2
Sep12-12, 11:03 PM
HW Helper
Thanks
PF Gold
LCKurtz's Avatar
P: 7,568
Quote Quote by SMA_01 View Post
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
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.
SMA_01
#3
Sep13-12, 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.

LCKurtz
#4
Sep13-12, 11:29 AM
HW Helper
Thanks
PF Gold
LCKurtz's Avatar
P: 7,568
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?
SMA_01
#5
Sep13-12, 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...
LCKurtz
#6
Sep13-12, 06:57 PM
HW Helper
Thanks
PF Gold
LCKurtz's Avatar
P: 7,568
Quote Quote by LCKurtz View Post
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?
Quote Quote by SMA_01 View Post
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.....?
SMA_01
#7
Sep13-12, 11:11 PM
P: 218
So, 2*2^k=2^(k+1), is that right?
LCKurtz
#8
Sep14-12, 11:32 AM
HW Helper
Thanks
PF Gold
LCKurtz's Avatar
P: 7,568
Quote Quote by SMA_01 View Post
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?
SMA_01
#9
Sep15-12, 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