# n choose k proof with mathematical induction

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.

• What is your definition of $\binom{n}{k}$? – Mark May 8 at 22:57
• Frankly saying, English is not my native language, so something may be wrong in my questions. And I really don't understand what do you mean, when asking me about definition. Maybe this will answer your question: n is the number of things to choose from, and we choose k of them, no repetition, order doesn't matter. $\binom nk=\frac{n!}{k!(n-k)!}$ is also known as the Binomial Coefficient – Pavel Stepanov May 8 at 23:02
• Yes, this is what I meant. Because some define $\binom{n}{k}$ like you did here, others just define it as $\frac{n!}{k!(n-k)!}$. All the definitions are equivalent, but we have to start from something. I'll write an answer soon. – Mark May 8 at 23:06

## 1 Answer

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.

• Feeling myself like a dumb-head... First of all I'm shy, because I've found the same question after I asked my question: link But still it's not fully clear for me. In mentioned book I've noticed, that exercise is for experienced reader. Think that for now I'm not so experienced to understand it in general. Anyway @Mark thanks a lot! – Pavel Stepanov May 8 at 23:56
• You're welcome. If you keep learning mathematics then experience will come. Of course at the beginning things are more difficult. – Mark May 9 at 0:02