-5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

\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}$.

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.