Binomial coefficient proof for ${n\choose m-1}+{n\choose m}={n+1\choose m}$

Question

I need to prove the following: ${n\choose m-1}+{n\choose m}={n+1\choose m}$, $1\leq m\leq n$.

With the definition: ${n\choose m}= \left\{ \begin{array}{ll} \frac{n!}{m!(n-m)!} & \textrm{für \(m\leq n\)} \\ 0 & \textrm{für \(m>n\)} \end{array} \right.$

and $n,m\in\mathbb{N}$.

I'm not really used to calculations with factorials and can't make much sense from it...

Answer 1

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

Answer 2

This is the most simplest answer,

$$\begin{align*}\begin{split} {n\choose m-1}+{n\choose m} &= \frac{m}{m}\cdot\frac{n!}{(m-1)!(n-m+1)!}+\frac{(n+1-m)}{(n+1-m)}\cdot\frac{n!}{m!(n-m)!}\\ &=\frac{mn!}{(m)!(n-m+1)!}+\frac{(n+1-m)n!}{m!(n+1-m)!} \\ &=\frac{mn!+(n+1)n!-mn!}{(m)!(n-m+1)!}\\ &=\frac{(n+1)n!}{(m)!(n-m+1)!} \\ &=\frac{(n+1)!}{(m)!(n-m+1)!} ={n+1\choose m}\end{split}\end{align*}$$

Answer 3

$$\begin{align*} \frac{n!}{(m-1)!(n-m+1)!} + \frac{n!}{m!(n-m)!} &= \frac{n!}{(m-1)!(n-m)!(n-m+1)} + \frac{n!}{(m-1)!(n-m)!m}\\ &= \frac{n!}{(m-1)!(n-m)!}\left[\frac1{n-m+1}+\frac1m\right]\\ &= \frac{n!}{(m-1)!(n-m)!}\cdot\frac{n+1}{m(n-m+1)}\\ &= \frac{(n+1)!}{m!(n-m+1)!} \end{align*}$$

Answer 4

Do it intuitively: assume you have n+1 objects from which you want to choose m. Now divide your n+1 objects into two groups: one that includes n objects and one group with 1 (specific) object. Choosing m from n+1 is equivalent to choosing m out of the first group (these exclude the one specific object) PLUS choosing m-1 out of n and adding while always that one specific object to them.

Answer 5

This is combinatorial proof maybe you like it Let yo have have a set whit $n$ elements and you want choose $m+1$ elements. Divide the set to two set that one of them has one element an the other one hase $n-1$ elements. now if you want to choose $m+1$ element you can do it in two ways

or you chose $m$ elements from $n$ elements' set and choose one element from singelton or choose $m+1$ elements from $n $ elements' set and choose nothing from singelton

Answer 6

So $$ n+1\choose m $$ means the number of ways to choose $m$ elements out of $n+1$. Now fix one element out of $n+1$. This element can be among these $m+1$, to pick the rest we need to pick $n\choose m-1$, or this element is not among these $m$, and we should pick then $n\choose m$ elements. Since this is exactly the number of ways to choose $m$ out of $n+1$ elements, the required result follows.

Answer 7

Simpler than the simplest, simplify by $n!$, $m!$ and $(n-m+1)!$: $$\frac{{n\choose m-1}+{n\choose m}}{n+1\choose m}=\frac{\frac{n!}{(m-1)!(n-m+1)!}+\frac{n!}{m!(n-m)!}}{\frac{(n+1)!}{m!(n-m+1)!}}= \frac{\frac1{1.m^{-1}}+\frac{1}{1.(n-m+1)^{-1}}}{\frac{n+1}{1.1}}=1.$$

Answer 8

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \color{#c00000}{{\pars{1 + z}^{n + 1} \over z^{k + 1}}}& ={\pars{1 + z}\pars{1 + z}^{n} \over z^{k + 1}} =\color{#c00000}{% {\pars{1 + z}^{n} \over z^{k + 1}} + {\pars{1 + z}^{n} \over z^{k}}} \end{align}

Then, \begin{align} \sum_{m\ =\ 0}^{n + 1}{n + 1 \choose m}z^{m - k - 1} &=\sum_{m\ =\ 0}^{n}{n \choose m}z^{m - k - 1} +\sum_{m\ =\ 0}^{n}{n \choose m}z^{m - k} \\[5mm]z^{-k - 1} + \sum_{m\ =\ 1}^{n + 1}{n + 1 \choose m}z^{m - k - 1} &=z^{-k - 1} + \sum_{m\ =\ 1}^{n}{n \choose m}z^{m - k - 1} +\sum_{m\ =\ 1}^{n + 1}{n \choose m - 1}z^{m - 1 - k} \\[5mm]z^{n - k} + \sum_{m\ =\ 1}^{n}{n + 1 \choose m}z^{m - k - 1} &=\sum_{m\ =\ 1}^{n}{n \choose m}z^{m - k - 1} +\sum_{m\ =\ 1}^{n}{n \choose m - 1}z^{m - 1 - k} + z^{n - k} \end{align}

$$ \sum_{m\ =\ 1}^{n}\color{#c00000}{{n + 1 \choose m}}z^{m - k - 1} =\sum_{m\ =\ 1}^{n}\bracks{\color{#c00000}{{n \choose m} + {n \choose m - 1}}} z^{m - k - 1} $$

$$ \color{#66f}{\large{n + 1 \choose m}} =\color{#66f}{\large{n \choose m} + {n \choose m - 1}}\,,\qquad 1\ \leq\ m\ \leq\ n $$