# An algebraic proof that a set has $2^n$ subsets. (I'm looking for an inductive argument.)

There will be duplicates of this, so let me explain why I am asking:

I have become blind to what it may be, so I want hints. I am blind because I can do it "combinatorially".

The question wishes me to prove using induction that a n-element set has $2^n$ subsets.

Combinatorial proof

Consider the set $S=\{x_1,x_2,...,x_n\}$, we have a choice, do we include or exclude $x_i$ from our subset? This choice is independent (regardless of what we chose previously we will always have 2 options). There are $n$ decisions, so by the axiom of choice there are $2^n$ ways to choose subsets. We have now established that there are $2^n$ subsets.

There is no induction here. Surely is is a proof though?

Possible algebraic (and inductive proof)

I can show that there is a 1:1 correspondence between subsets and the string that contains Y at position i, if $x_i$ is in the subset, and N otherwise. This defines $^nC_r$ as $\frac{n!}{r!(n-r)!}$ (as a multinomial coefficient, or right from the axiom) I can then say:

$\sum^n_{i=0}^nC_i=2^n$

(Not entirely sure how to say it formally)

This is because $^nC_i$ denotes the number of ways to choose i things, so the sum from 0 to n is the number of ways to choose a subset o any length between 0 and n, which is all possible subsets, which we established was $2^n$

I'd have no idea how to prove this by induction. BUT it feels very combinatoric anyway.

Is there an inductive proof?

I did peek at some, the best example of what makes this different is:

Prove by induction: For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $2^N$ subsets.

This uses exactly the same logic as the proof of "Pascal's relation" which is certainly combinatoric. The point of this chapter is to get the reader to stop thinking of $^nC_r$ as $\frac{n!}{r!(n-r)!}$ and see it with combinatorial goggles. Unfortunately I never thought of $^nC_r$ like that (I would have seen the binomial theorem at AS level, 5 years ago, and the "axiom of choice" is trivial, I would have understood factorials 8 years ago) I also understand that there is quite a bit of overlap between some parts of Abstract Algebra and combinatorics, perhaps I am being too strict?

-
@labbhattacharjee EXACTLY the same proof as the linked one is the accepted answer of that. – Alec Teal Mar 16 '14 at 15:22
Answer: I was being too strict. – Alec Teal Mar 16 '14 at 15:40
This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. – user68061 Mar 16 '14 at 15:58
@user68061 I am the question asked, this is my answer, the proof above is pretty close to the arguments in both question linked, I am being to strict about what I call "combinatorial in style" – Alec Teal Mar 16 '14 at 16:00

For $\;n=0,1,2\;$ the case is clear. Suppose it is true for $\;n\;$ , show for $\;n+1\;$ . So suppose $\;A:=\{a_1,...,a_n,a_{n+1}\}\;$ is our set, and out $\;B:=\{a_1,...,a_n\}\;$.
The gist of all this business is to observe that any subset of $\;A\;$ is either a subset of $\;B\;$ or a subset of $\;B\;$ union the singleton $\;\{a_{n+1}\}\;$ (why?!), and thus the number of subsets in $\;A\;$ is twice that of $\;B\;$ ...and from here we get by the induction hypothesis that
$$|P(A)|=2|P(B)|=2\cdot2^n=2^{n+1}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\square$$