Prove there are exactly $\binom{n}{k}$ subsets of $\{1,\ldots,n\}$ with $k$ elements I want to prove that for $n,k \in \mathbb{N}_0$ and $k \le n$ there are exactly $\binom{n}{k}$ subsets of $\{1,\ldots,n\}$ with $k$ elements.

I thought about a proof by induction over $n$, but I'm struggling to prove the induction step. What I have so far is:
Let $n = 0$. Then there are exactly $\binom{0}{0} = 1$ subset of $\{\} = \emptyset$ with $0$ elements, namely $\emptyset$.
Assume the statement is true for $n$. I need to prove that there are exactly $\binom{n+1}{k}$ subsets of $\{1,\ldots,n,n+1\}$ with $k$ elements.
Do I need a second induction over $k$?
 A: Assume that you want the element $n+1$ in your new set, then you need to choose $k-1$ elements between the $n$ first elements, so $\binom {n}{k-1}$. Now, assume that you don't want the element $n+1$ in your new set, then you need to choose $k$ elements between $n$ first elements, so $\binom {n}{k}$. In total, you get:
$$\binom {n}{k-1} + \binom {n}{k} = \binom{n+1}{k}$$
Basically, you should try to abuse the propriety you have as true as much as possible. So try to get your problem of choosing $n+1$ items to a problem of choosing $n$ items, because you know the formula for that.
Apart from induction, you can also prove this through simple reasoning. What you need is $k$ elements from a set of $n$ elements. These elements will not be ordered. So you just need to "choose" $k$ elements from $n$, and the formula for that is $$\binom {n}{k}$$
A: There are various ways of doing this. But for induction a subset of size $k$ in a set with $n+1$ elements either contains the additional element or it doesn't. If it does, you are looking for $k-1$ elements from the first $n$ and if it doesn't you are looking for $k$ elements from the first $n$. (This should remind you of Pascal's triangle.) You need your inductive hypothesis to give you both these numbers. You would therefore be wise to prove this for $n$ and all $k$ before moving to consider $n+1$.
A: Take the set $\{1,2,\dots,n\}$. Label each number of this set with $0$ or $1$. If we label some number $i$ with $1$ then we include that number $i$ to our set, and $0$ otherwise. So the number of subsets containing $k$-elements is equal to the number of strings length $n$ containing exacrly $k$ $1$'s. So the number of such strings is $C_n^k=\frac{n!}{k!(n-k)!}$
A: The formula for choosing a set or group of $k$ elements out of $n$ just is $n \choose k$. I mean, that formula is expressed as '[out of] $n$ choose $k$'
So I suppose what you're really asking is: why is it that
$${n \choose k} = \frac{n!}{k!(n-k)!}$$
Or, in other words: why are there $\frac{n!}{k!(n-k)!}$ ways to choose $k$ elements out of $n$?
Well, here is one way to think about it:
On way to choose $k$ elements out of $n$ is to randomly line up all the $n$ elements, and then pick the first $k$ elements as your subset.  
Now, notice that there are $n!$ ways to line up the $n$ elements. However, also notice that after we have done that, we can shuffle any of the first $k$ elements around, while still ending up with those same $k$ elements as our subset. So, since we can shuffle those $k$ elements around in $k!$ ways, we need to divide by $k!$. Likewise, we can shuffle around the remaining $n-k$ elements in the line-up without changing the eventual outcome of the nature of the subset. So, we also need to divide by $(n-k)!$. We thus end up with exactly:
$$\frac{n!}{k!(n-k)!}$$
ways to choose $k$ elements out of $n$ elements.  And that is how $n \choose k$ is defined.
