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

1. ### SMA_01

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

2. ### LCKurtz

8,454
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
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. ### LCKurtz

8,454
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
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

8,454
Yes, so.....?

7. ### SMA_01

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

8. ### LCKurtz

8,454
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
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