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

by SMA_01
Tags: equal, number, proof, subsets
 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: $\sum^{k=0}_{n}$ (n k)=2n
HW Helper
Thanks
PF Gold
P: 7,662
 Quote by SMA_01 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: $\sum^{k=0}_{n}$ (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.
 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.
 HW Helper Thanks PF Gold P: 7,662 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?
 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...
HW Helper
Thanks
PF Gold
P: 7,662
 Quote by LCKurtz 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 by SMA_01 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.....?
 P: 218 So, 2*2^k=2^(k+1), is that right?
HW Helper
Thanks
PF Gold
P: 7,662
 Quote by SMA_01 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?
 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

 Related Discussions Calculus & Beyond Homework 0 Set Theory, Logic, Probability, Statistics 2 Set Theory, Logic, Probability, Statistics 2 Linear & Abstract Algebra 22 Introductory Physics Homework 9