# proving combinatorics identity - $\sum_{k=0}^m{n-k \choose m-k}={n+1 \choose m}$

Prove that for every $n \ge m \ge 1 , \sum_{k=0}^m{n-k \choose m-k}={n+1 \choose m}$

I've tried saying that the RHS represents the number of binary series with m "1" 's and n+1-m "0"'s, but I couldn't find out what k represents at the LHS. Thanks

## 4 Answers

You can think of LHS as $$\sum_{k=0}^{m} \dbinom{n-k}{n-m}$$ hence, you count the number of binary series starting with exactly k "1"s. For example when $k=0$, the first term must be "0", which has $\dbinom{n}{n-m}$ combinations, and when $k=1$ the number of binary series starting with exactly one "1" has $\dbinom{n-1}{n-m}$ combinations (since you need the second term in the sequence to be "0"), and so on.

These sum to exactly the number of possible binary series with m "0"s and n-m+1 "1"s as you described. Hope this helps.

In an $(n+1-m)\times m$ grid, there are $n+1 \choose m$ routes (Think of the choices of when to go Up among the $n+1$ binary choices of Up and Right to get from A to B).

Let $R_k$ denote the routes up to that node but with a decision of Right turn next. Every route to $B$ includes only one of these $R_0, R_1, \dots,$ or $R_m$ (go right, rest is up) choices.

Equivalently, denote Right by $0$ and Up by $1$ so that we sum the choices with tail $0, 01, 011, 0111, \dots,$ and $01\dots 1$ exhausting the $m$ ones. $\newcommand{\angles}{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}{\overline{#1}} \newcommand{\pars}{\left(\, #1 \,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\, #2 \,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\, #1 \,\right\vert}$

\begin{align} \color{#f00}{\sum_{k = 0}^{m}{n - k \choose m - k}} & = \sum_{k = 0}^{m}{-n + k + m - k - 1 \choose m - k}\pars{-1}^{m - k} = \pars{-1}^{m}\sum_{k = 0}^{m}\pars{-1}^{k}{m - n - 1 \choose m - k} \\[3mm] & = \pars{-1}^{m}\sum_{k = 0}^{m}\pars{-1}^{k}\ \overbrace{% \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{m - n - 1} \over z^{m - k + 1}}\, {\dd z \over 2\pi\ic}}^{\ds{=\ {m - n - 1 \choose m - k}}} \\[3mm] & = \pars{-1}^{m}\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{m - n - 1} \over z^{m + 1}} \sum_{k = 0}^{m}\pars{-z}^{k}\,{\dd z \over 2\pi\ic} \\[3mm] & = \pars{-1}^{m}\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{m - n - 1} \over z^{m + 1}} {\pars{-z}^{m + 1} - 1\over \pars{-z} - 1}\,{\dd z \over 2\pi\ic} \\[3mm] & = \overbrace{% \oint_{\verts{z} = 1^{-}}\pars{1 + z}^{m - n - 2}\,{\dd z \over 2\pi\ic}} ^{\ds{=\ 0}}\ +\ \pars{-1}^{m}\ \overbrace{% \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{m - n - 2} \over z^{m + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ {m - n - 2 \choose m}}} \\[3mm] & = \pars{-1}^{m}{m - n - 2 \choose m} = \pars{-1}^{m}{-m + n + 2 + m - 1 \choose m} \pars{-1}^{m} = \color{#f00}{{n + 1 \choose m}} \end{align}

\begin{align} \sum_{k=0}^m\binom{n-k}{m-k} &=\sum_{k=0}^m\binom{n-k}{n-m}\tag{1}\\ &=\binom{n+1}{n-m+1}\tag{2}\\[3pt] &=\binom{n+1}{m}\tag{3} \end{align} Explanation:
$(1)$: $\binom{n}{k}=\binom{n}{n-k}$
$(2)$: Equation $(9)$ from this answer
$(3)$: $\binom{n}{k}=\binom{n}{n-k}$

• would the downvoter care to comment? – robjohn Jun 13 '16 at 14:38