Binomial coefficient proof for ${n\choose m-1}+{n\choose m}={n+1\choose m}$ 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...
 A: 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*}$$
A: $$\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}$$
A: 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. 
A: 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.
A: $\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
$$

A: $$\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*}$$
A: 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
A: 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.$$
A: I struggled with this problem too a bit and I feel like the answers here don't explain all the steps here.
For my solution, there are three key insights: that ${m! = m(m-1)!}$ and that ${(m + 1)! = m!(m+1)}$, and that if the proposition is true, then ${m!(n - m + 1)!}$ must be valid as the common denominator for ${n\choose m}$ and ${n\choose m - 1}$, because we know that ${{n+1\choose m} = \frac{(n + 1)!}{m!(n + 1 - m)!} = \frac{(n + 1)!}{m!(n -m + 1)!}}$.
With that in mind, the question is how to transform ${n \choose m}$ and ${n \choose m - 1}$ so that they both share the denominator ${m!(n - m + 1)!}$.
Let's start with ${n \choose m - 1}$:
$$\begin{align}
{n \choose m - 1} &= \frac{n!}{(m-1)!(n - m + 1)!}\\
&= \frac{m!}{m!} \cdot \frac{n!}{(m-1)!(n - m + 1)!}\\
&= \frac{m!n!}{m!(m-1)!(n -m + 1)!}\\
&= \frac{m(m-1)!n!}{m!(m-1)!(n-m+1)!}\\
&= \frac{n!m}{m!(n-m+1)!}
\end{align}$$
Now, ${n \choose m}$, the key insight here is that ${(n-m+1)(n-m)! = (n-m+1)!}$ (let ${k = n-m}$, then we see that ${k!(k+1) = (k+1)! = (n-m+1)!}$):
$$\begin{align}
{n \choose m} &= \frac{n!}{m!(n - m)!}\\
&= \frac{(n -m + 1)}{(n-m+1)} \cdot \frac{n!}{m!(n - m)!}\\
&= \frac{n!(n-m+1)}{m!(n-m+1)(n-m)!}\\
&= \frac{n!(n-m+1)}{m!(n-m+1)!}\\
\end{align}$$
Now, finally, we can do:
$$\begin{align}
\frac{n!m}{m!(n-m+1)!} + \frac{n!(n-m+1)}{m!(n-m+1)!} &= \frac{n!m + n!(n-m+1)}{m!(n-m+1)!}\\
&= \frac{n!(n + 1)}{m!(n + 1 - m)!}\\
&= \frac{(n + 1)!}{m!(n+1-m)!}\\
&= {n + 1 \choose m}
\end{align}$$
