n choose k proof with mathematical induction

Question

I'm reading "what is Mathematics" written by Richard Courant. I'm trying to do all the exercises. It's really not easy for me, even though exercises are really easy. For now I'm trying to solve n choose k proof exercise. I have to proof $\binom nk=\frac{n!}{k!(n-k)!}$ using mathematical induction. I've tried different ways, I've read different articles about combinatorics and binomial coefficients, but still no use. Please help.

Answer 1

We'll do it by induction. For $n=1$ you just have to check the formula is true.

Suppose the statement is true for $n-1$ when $n\geq 2$. This means for each $0\leq k\leq n-1$ we have $\binom{n-1}{k}=\frac{(n-1)!}{k!((n-1)-k)!}$. Now we want to prove that for each $0\leq k\leq n$ we have $\binom{n}{k}=\frac{n!}{k!(n-k)!}$. If $k=0$ or $k=n$ then it is easy to find $\binom{n}{k}$ so just check the formula is true. Now let $1\leq k\leq n-1$. I say that $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. Why is that? Well, we have $n$ objects, let's call them $x_1,...,x_n$. We want to choose $k$ of them without repetitions and without caring about order. We can split the options to do that into two parts: options where we choose the element $x_n$ and the options where we do not choose $x_n$. In options where we choose $x_n$ all we have to do is choose $k-1$ more elements from $x_1,...,x_{n-1}$ and the number of ways to do this is $\binom{n-1}{k-1}$ by definition. In options where we do not choose $x_n$ we just have to choose $k$ elements from $x_1,...,x_{n-1}$ and the number of ways to do this is $\binom{n-1}{k}$. Hence the number of ways to choose $k$ elements from $x_1,...,x_n$ is $\binom{n-1}{k-1}+\binom{n-1}{k}$. On the other hand by definition the number of ways is $\binom{n}{k}$, so we conclude that $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. And from here just use the induction assumption, this is pure algebra.