Prove that $P(X)$ has exactly $\binom nk$ subsets of $X$ of $k$ elements each. Let set $X$ consist of $n$ members. $P(X)$ is power set of $X$.
Prove that set $P(X)$ has exactly $$\binom nk = \frac{n!}{k!(n-k)!}$$ subsets of $X$ of $k$ elements each. Hence, show that $P(X)$ contains $2^n$ members.
Hint: use the binomial expansion of $(1 + 1)^n$.
I'm trying to get more into math (proof writing first) so I got this from a book about Real Analysis. It's a short first sub-chapter which was an intro review of set theory and I have absolutely no idea how to do this particular problem given what has been said in 8 pages.
I 'know' that it's true, since I've tried it. I can also somewhat prove that $P(X)$ has $2^n$ elements thinking of binary numbers. I can also see that the binomial expansion of $(1 + 1)^n$ does tell the number of subsets of $X$ that has $k$ elements via the coefficients. I just don't know how they all fit together given that the author thinks they should.
I've also seen some questions in here proving the summation of $\binom nk = 2^n$, which was suppose to help, but I couldn't understand them at all given my limited math/combinatorics knowledge.
 A: Let $X$ a set with $n$ elements so to select a subset of $X$ with $k$ elements we have to choose $k$ elements from the $n$ elements of $X$ so  we have $n\choose k$ possibilities of such choices. 
The cardinal of $\mathcal{P}(X)$ is the number of all subset with $k$ elements for $k=0,\ldots,n$ so 
$$\mathrm{card}(\mathcal{P}(X))=\sum_{k=0}^n {n\choose k}=(1+1)^n=2^n.$$
A: I think some hints might be more appropriate here than actually answering the question:
1) If you take $k$ out of $n$ elements, you automatically also take $n-k$ out of $k$ elements - the other ones. The order of these elements doesn't matter.
2) All subsets of a finite set with $n$ elements have a certain amount of elements: $|\mathcal{P}(X)|=$the number of subsets = the number of subsets having no elements + the number of subsets having exactly one element+...+the number of subsets having exactly $n$ elements. How does this translate to $(1+1)^n$ using the first part of your question?
A: Personally, I'd take apart that fraction for the binomial co-efficient that has pieces that can be explained.
First, consider the idea of choosing $k$ elements from the set of $n$ elements where order matters initially.  This should produce the $\frac{n!}{(n-k)!}$ expression that is a starting point.
Second, order doesn't matter here and thus this over counts the group where $k>1$ since one could re-order elements here.  Thus, there is something to be said for dividing the initial quotient by $k!$ since this is the number of permutations of $k$ elements.
At least this would be my suggestion for how to go about doing a construction proof of what you want.  If you want something to consider, look at Generating Functions where if you consider the expansion of $(x+1)^n$ and take the co-efficient of $x^k$ this would be the binomial coefficient.  If you substitute $x=1$ then you would see how the $(1+1)^n$ is applicable here.
