Strong Induction problem related to combinatorics

In summary, the number of subsets of an n-element set is 2 times the number of subsets of an n-1 element set. This can be proven through a bijection between the subsets that contain the nth element and those that do not, indicating that adding 1 to n doubles the size of the set of subsets.
  • #1
starcoast
9
0

Homework Statement



How is the number of subsets of an n-element set related to the number of subsets of an (n-1) element set? Prove that you are correct.

Homework Equations





The Attempt at a Solution


So, clearly the the number of subsets in an n element set is 2[tex]^{n}[/tex]. So the number of subsets of an n-element set is 2*(the number of subsets of an n-1 element set). But I'm having trouble proving it. I'm pretty sure strong induction is what I need to use here, but we haven't talked about it in class and the material in the book is confusing, with little explanation (our book is mostly learn-on-your-own examples). If someone could walk me through the proof, or at least help me get to the correct inductive hypothesis, I would be really grateful.
 
Physics news on Phys.org
  • #2
welcome to pf!

hi starcoast! welcome to pf! :smile:

hint: split the set of subsets of an n-element set into two :wink:
 
  • #3


tiny-tim said:
hi starcoast! welcome to pf! :smile:

hint: split the set of subsets of an n-element set into two :wink:

Okay, I used that bijection instead of induction, but something about it doesn't feel like I proved it for all n. How does this look?

We divide the subsets of a given n-element set T into two sets: the set of subsets that contain the nth element in the set, S, and the set of subsets that do not contain the nth element in the set, P. We find a bijection between the two sets: set S can be constructed from set P by adding the nth term of set T to the end of each term in set P. This bijection indicates that by adding 1 to n, we double the size of the set of subsets. In other words, Sn = 2 * Sn-1
 
  • #4
starcoast said:
Okay, I used that bijection instead of induction, but something about it doesn't feel like I proved it for all n. How does this look?

looks ok to me …

you've proved it for any n :smile:​
 

FAQ: Strong Induction problem related to combinatorics

What is the Strong Induction problem related to combinatorics?

The Strong Induction problem related to combinatorics is a mathematical proof technique used to prove statements about integers that depend on previous integers. It is a powerful method that extends the principle of mathematical induction by allowing multiple base cases.

How does the Strong Induction method work in combinatorics?

The Strong Induction method in combinatorics starts by proving the base case, which is usually the smallest integer for which the statement is true. Then, the method assumes that the statement is true for all integers up to a certain value and uses this assumption to prove that the statement is also true for the next integer. This process is repeated until the desired result is proven for all integers.

What are the advantages of using Strong Induction in combinatorics?

The Strong Induction method in combinatorics allows for more flexibility in proving statements that depend on previous integers. It also allows for multiple base cases, which can make the proof process more efficient. Additionally, it can be used to prove more complex statements that cannot be proved using regular mathematical induction.

Can the Strong Induction method be used to prove all statements in combinatorics?

No, the Strong Induction method cannot be used to prove all statements in combinatorics. It is only applicable to statements that depend on previous integers. Some statements may require different proof techniques such as direct proof or proof by contradiction.

What are some common mistakes to avoid when using Strong Induction in combinatorics?

One common mistake when using Strong Induction in combinatorics is assuming that the statement is true for all integers without proving the base case. It is also important to correctly identify the statement and the correct assumption to make for the next integer. Additionally, it is important to clearly state the inductive hypothesis and explain how it is used in the proof.

Similar threads

Prove every subset of countable set is either finite or else countable
Replies
1
Views
1K
Do these two statements imply an underlying induction proof?
Replies
7
Views
868
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
Replies
4
Views
904
Proof by induction for rational function
Replies
7
Views
868
Combinatorics: looking for an alternative solution
Replies
7
Views
2K
Problem on a set which is a subset of a finite set
Replies
3
Views
1K
Proving Completeness property of ##\mathbb{R}## using Dedekind cuts
Replies
20
Views
3K
Is the Empty Set an Inductive Set?
Replies
2
Views
5K
A quite verbal proof that if V is finite dimensional then S is also....
Replies
34
Views
2K
Need help with a variation of the domino tiling problem
Replies
1
Views
794

Hot Threads

Recent Insights

Back
Top