4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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. enter image description here

$\endgroup$
2
$\begingroup$

$\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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#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}$

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

$\endgroup$
2
$\begingroup$

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

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

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.