How Does the Power Set Size Double with Each Additional Element?

[Samuelb88]

Homework Statement

Let [n] denote the set consisting of the first n natural numbers 1, 2, 3, ..., n. Use induction to prove that the power set P([n]) has exactly 2^n elements.

The Attempt at a Solution

1) Base case: P([1]) = {{1}, null}. 2^1 = 2 elements.
2) Inductive step: Assume P([n]) has 2^n elements and prove P([n+1]) has 2^(n+1) elements.

I am stuck on the inductive step. I am not sure how to prove P([n+1]) has twice as many elements as P([n]). Through numerical experimentation for some small values of n, I've found that the number of new subset elements for each value of n is can be "represented" by pascal's triangle so I tried expressing the numbers of elements for P([n]) as a sum of the binomial coefficients:

[tex]2^n = \sum_{j=1}^{n} \frac{n(n-1)...(n-j+1)}{j!}\right)[/tex]

And by multiplying both sides by 2 would yield 2^(n+1) on the LHS, however, I can't seem to equate the RHS to:

[tex] \sum_{j=1}^{n+1} \frac{(n+1)(n)(n-1)...(n-j+2)}{j!}\right)[/tex]

Am I on the right track? Does this idea work? Any hints would be great! :)

 

[Dick]

You are making this too complicated. P(n) is all of the subsets of {1,...,n}. P(n+1) is all of the subsets of {1,...,n,n+1}. For every subset in P(n) you can make 2 subsets of P(n+1) by either including the element n+1 or not.

 

[Samuelb88]

Right, that makes sense. But how can I apply that idea to my inductive step?

 

[Dick]

Right, that makes sense. But how can I apply that idea to my inductive step?

Ok, then the number of elements in P(n+1) is twice the number of elements in P(n), isn't it?

 

[Samuelb88]

Correct. But that seems like I am merely "conjecturing" that P(n+1) has twice as many elements as P(n), not proving.

PS: Sorry, I made a typo in my original post. It use to read, "...assume P([n+1])..."

2) Inductive step: Assume P([n]) has 2^n elements and prove P([n+1]) has 2^(n+1) elements.

 

[HallsofIvy]

Correct. But that seems like I am merely "conjecturing" that P(n+1) has twice as many elements as P(n), not proving.

PS: Sorry, I made a typo in my original post. It use to read, "...assume P([n+1])..."

No, you are not "conjecturing" anything. Every set in P(n+1) either contains n+1 or it doesn't. If it doesn't contain n+1 then it is in P(n). How many such sets are there?

If it does contain n+ 1 then it is a union, [itex]\{n+1\}\cup A[/itex] where A does NOT include n+1. How many such sets are there?