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

In summary, the conversation discusses proving that the number of subsets of a set with n elements is equal to 2n using mathematical induction. The initial proposition is that a set with a single element has two subsets, and the induction step involves showing that adding another element to a set with k elements results in 2k more subsets. The conversation also touches on the use of binomial coefficients in this proof.
  • #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
 
Physics news on Phys.org
  • #2
SMA_01 said:

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
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
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
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 said:
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 said:
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
So, 2*2^k=2^(k+1), is that right?
 
  • #8
SMA_01 said:
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
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:
 

1. What is the formula for finding the number of different subsets of a set A?

The formula for finding the number of different subsets of a set A is 2^n, where n is the number of elements in set A.

2. How does the formula for finding the number of different subsets of a set A work?

The formula works by using the concept of binary numbers. Each element in set A corresponds to a digit in a binary number, and the presence or absence of an element in a subset is represented by 1 or 0 respectively. Therefore, there are 2^n possible combinations of elements, resulting in 2^n different subsets.

3. Can you provide an example of using the formula for finding the number of different subsets of a set A?

Sure, let's say we have a set A with 3 elements: {1, 2, 3}. Using the formula 2^n, we get 2^3 = 8. Therefore, there are 8 different subsets of set A: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.

4. Is the formula for finding the number of different subsets of a set A applicable to all sets?

Yes, the formula is applicable to all sets, regardless of the number of elements in the set. However, it is important to note that the formula only calculates the number of different subsets, and does not provide the actual subsets themselves.

5. What is the significance of knowing the number of different subsets of a set A?

Knowing the number of different subsets of a set A can be useful in various mathematical and scientific applications, such as probability calculations, combinatorics, and set theory. It can also help in understanding the complexity of a problem or system by considering all possible combinations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
456
  • Calculus and Beyond Homework Help
Replies
4
Views
461
  • Calculus and Beyond Homework Help
Replies
7
Views
339
  • Calculus and Beyond Homework Help
Replies
2
Views
823
  • Calculus and Beyond Homework Help
Replies
3
Views
995
  • Calculus and Beyond Homework Help
Replies
4
Views
951
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
34
Views
2K
Replies
23
Views
1K
Back
Top