Show $\sum_{k=m}^n {k \choose r} = {n+1 \choose r+1} - {m \choose r+1}$ $$\sum_{k=m}^n {k \choose r} = {n+1 \choose r+1} - {m \choose r+1}$$  
I'm stumped. Tried algebraically decomposing each side but I can't make ends meet. 
 A: I'll reference Wikipedia's Page on this, rewriting the proof to make it more easily comprehendible
$$
\sum_{k=m}^n\binom{k}{r}$$
$$= \sum_{k=m}^n\left[\binom {k+1}{r+1}- \binom{k}{r+1}\right]$$
$$= \color{red}{{m+1 \choose r+1}}-{m \choose r+1}\\\color{green}{+{m+2 \choose r+1}}\color{red}{-{m+1 \choose r+1}}\\\color{blue}{+{m+3 \choose r+1}}\color{green}{-{m+2 \choose r+1}}\\+\color{purple}{{m+4 \choose r+1}}\color{blue}{-{m+3 \choose r+1}}\\+\cdots+\\+\color{fuchsia}{{n \choose r+1}}\color{teal}{-{n-1 \choose r+1}}\\+{{n+1 \choose r+1}}\color{fuchsia}{-{n \choose r+1}}
$$
We note that everything will cancel itself out except the second term of the first line and the first term of the last line. Our sum is thus
$$=\binom{n+1}{r+1}-\binom m{r+1}$$
A: There is a nice combinatorial way to prove this without algebra by telling a story.
Consider $n+1$ items labeled $\{I_1, I_2, \ldots, I_{n+1}\}$.  The right hand side is the number of ways to pick $r+1$ items among the $n+1$ items excluding the cases where one chooses all $r+1$ items among the first $m$ items.  In other words, the right hand side is number of ways to pick $r+1$ items such that at least one comes from $\{I_{m+1}, I_{m+2}, \ldots, I_{n+1}\}$.
But let's count this in a different way.  If $L$ is the highest item number in the choice of $r+1$ items, then $L= m+1, \ldots, n$ are exactly the possibilities.  For each case of $L$, we have ${L-1\choose r}$ choices.  This gives us $\sum_k {k\choose r}$, which is the left hand side!
No algebra needed (if you like these kind of counting stories).
A: Try to use combinatorics.
Consider number of different n+1 people grouping  that consist of m students,  and the remaining is teachers that are different ages with the following rule.
    1. r+1 people in a group.

    2. the group consist of 1 head and r members.

    3. the head have to be the oldest teacher in the group.

RHS : 
Choose r+1 people from n+1 people, we have $\displaystyle\binom{n+1}{r+1}$ possible groups, but there must not group only students, there is equal to $\displaystyle \binom{m}{r+1}$ groups. 
Then, we get the RHS.
Note if the group consist of at least 1 teacher, It will surely have a head.
LHS : Choose head first.
1) Choose a youngest people to be a head then there have only student be member $\displaystyle\binom{m}{r}$
2) Choose teacher who is 2nd youngest to be a head then there have a youngest teacher and m student for r people grouping, we get $\displaystyle\binom{m+1}{r}$ possible number to be a member.
and in the same way to choose the head from 3rd youngest to the oldest teacher, then we will get the LHS.
A: $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

An analytic approach:

\begin{align}
\sum_{k = m}^{n}{k \choose r} & =
\sum_{k = m}^{n}\oint_{\verts{z} = 1}{\pars{1 + z}^{k} \over z^{r + 1}}
\,{\dd z \over 2\pi\ic} =
\oint_{\verts{z} = 1}{1 \over z^{r + 1}}\sum_{k = m}^{n}\pars{1 + z}^{k}
\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\oint_{\verts{z} = 1}{1 \over z^{r + 1}}\,
\pars{1 + z}^{m}\,\,{\pars{1 + z}^{n - m + 1} - 1 \over \pars{1 + z} - 1}
\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\oint_{\verts{z} = 1}{\pars{1 + z}^{n + 1} \over z^{r + 2}}
\,{\dd z \over 2\pi\ic} -
\oint_{\verts{z} = 1}{\pars{1 + z}^{m} \over z^{r + 2}}
\,{\dd z \over 2\pi\ic} =
\bbx{\ds{{n + 1 \choose r + 1} - {m \choose r + 1}}}
\end{align}
