Strong Induction problem related to combinatorics

[starcoast]

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^{n}. 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.

 

[tiny-tim]

welcome to pf!

hi starcoast! welcome to pf!

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

 

[starcoast]

hi starcoast! welcome to pf!

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

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

 

[tiny-tim]

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 ​