proving combinatorics identity - $\sum_{k=0}^m{n-k \choose m-k}={n+1 \choose m}$
Solution 1:
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.
Solution 2:
$$
\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}$
Solution 3:
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.
Solution 4:
$\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}