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$?
Best Answer
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}$$