# show that $\begin{pmatrix} n+1 \\ m \end{pmatrix} = \begin{pmatrix} n \\ m \end{pmatrix} + \begin{pmatrix} n \\ m-1 \end{pmatrix}$

Given binomial coefficients, show that

$$\begin{pmatrix} n+1 \\ m \end{pmatrix} = \begin{pmatrix} n \\ m \end{pmatrix} + \begin{pmatrix} n \\ m-1 \end{pmatrix}$$ for $0 \leq m \leq n$

and use this to show by induction on n that:

$$\begin{pmatrix} n \\ m \end{pmatrix} =\frac{n!}{m!(n-m)!}$$ for $0 \leq m \leq n$

I managed to show that

$$\begin{pmatrix} n+1 \\ m \end{pmatrix} = \begin{pmatrix} n \\ m \end{pmatrix} + \begin{pmatrix} n \\ m-1 \end{pmatrix} = \frac{n+1!}{m!(n+1-m)!}$$

I started the proof by induction as such:

• Testing n=1:

If n=1, then m=1 as binomial coefficient is such that $0 \leq m \leq n$

$$\begin{pmatrix} 1 \\ 1 \end{pmatrix} =\frac{1!}{1!(1-1)!} =1$$

To check this I used the definition of binomial coefficient stating that $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ represent the coefficient of $x^1$ in $(1+x)^1$ that is $1$ It follows that $\begin{pmatrix} 1 \\ 1 \end{pmatrix} =\frac{1!}{1!(1-1)!} =1$ is true

• Assumption: Let's assume that the Proposition $P_n$ below is true:

$$\begin{pmatrix} n \\ m \end{pmatrix} =\frac{n!}{m!(n-m)!}$$

• Claim: The Proposition $P_{n+1}$ is true:

$$\begin{pmatrix} n+1 \\ m \end{pmatrix} = \frac{n+1!}{m!(n+1-m)!}$$

At this level I am stock to properly continue

Any input is much appreciated

\begin{align*} \binom{n}{m}+\binom{n}{m-1}&=\frac{n!}{m!(n-m)!}+\frac{n!}{(m-1)!(n-m+1)!}\\ &=\frac{(n-m+1)(n!)}{m!(n-m+1)!}+\frac{m(n!)}{m!(n-m+1)!}\\ &=\frac{(n+1)(n!)}{m!(n-m+1)!}\\ &=\frac{(n+1)!}{m!(n+1-m)!}\\ &=\binom{n+1}{m} \end{align*}

Another approach is:

To pick $m$ objects from $n+1$ objects, we have $\displaystyle\binom{n+1}{m}$ choices. Let $A$ be one of the $n+1$ objects. If $A$ is picked, then we have to pick $m-1$ objects from the remaining objects. The number of choices is $\displaystyle\binom{n}{m-1}$. If $A$ is not picked, then we have to pick $m$ objects from the remaining objects. The number of choices is $\displaystyle\binom{n}{m}$.

• The first method can't be used, since the aim of the exercise is to prove the formula with factorials. – Bernard May 26 '17 at 10:45
• @Bernard I missed that. You are right. – CY Aries May 26 '17 at 10:47

Hint:

$\dbinom nm$ is the coefficient of $x^m$ in the expansion of $(1+x)^n$. Write $$(1+x)^{n+1}=(1+x)(1+x)^n$$ and proceed with induction.

Use a Pascal argument, where $m\choose k$ is the number of $k$-element subsets of the set $\{1,\ldots,m\}$. Let $A$ be the number of subsets of $\{1,\ldots,m\}$ that do not contain $m$ and let $B$ be the complementary set. Then $\{1,\ldots,m\}$ is the disjoint union of $A$ and $B$. But $A$ has cardinality $m-1\choose k$ and $B$ has cardinality $m-1\choose k-1$. Done.

You are in a class with $n+1$ pupils. Now a group of $m$ pupils should be chosen out of all $n+1$ pupils. Either you belong to that group or not.

Now if you don't belong to the group there are $\binom{n}{m}$ possibilities. If you belong to it then there are $\binom{n}{m-1}$ possibilities.