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:


(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:


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?

  • $\begingroup$ math.stackexchange.com/questions/44908/… $\endgroup$ – lab bhattacharjee Mar 16 '14 at 15:19
  • $\begingroup$ @labbhattacharjee EXACTLY the same proof as the linked one is the accepted answer of that. $\endgroup$ – Alec Teal Mar 16 '14 at 15:22
  • $\begingroup$ Answer: I was being too strict. $\endgroup$ – Alec Teal Mar 16 '14 at 15:40
  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. $\endgroup$ – user68061 Mar 16 '14 at 15:58
  • $\begingroup$ @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" $\endgroup$ – 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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.