Lattice path: proof of $\sum_{k=0}^n{s+k \choose k}{n-k \choose m}={s+n+1 \choose s+m+1}$ I want to prove that
$\displaystyle\sum_{k = 0}^{n}
{s + k \choose k}{n - k \choose m} =
{s + n + 1 \choose s + m + 1}$ by using lattice paths.
In the case of R.H.S, it is clear that it is all cases of lattice paths of
$\left(s + m + 1\right) \times
\left(n - m\right)$.
However in the case of L.H.S, I think I should divide some cases, but I have no idea how to do it.
Please help me.
 A: Suppose $m < n$, and that your rectangle has height $s+m+1$ and width $n-m$.
Draw a horizontal line at height $y=m$. Given a lattice path, let $(x,m)$ be the last place where the path intersects this line. The possible values for $x$ are $0, 1, 2, \dots, n-m$. Let $k = n-m-x$ (or equivalently $x = n-m-k$). Then there are $\binom{x+m}{m} = \binom{n-k}{m}$ lattice paths from $(0,0)$ to $(x,m) = (n-m-k,m)$.
To finish the lattice path, you still need to choose a path starting at $(x,m) = (n-m-k,m)$ and ending at $(n-m,s+m+1)$. Notice that we assumed above that $(x,m)$ was the last point where the lattice path was at height $m$. This means the first part of the second half of the path must begin by going UP. This is equivalent to choosing a lattice path starting at $(x,m+1) = (n-m-k,m+1)$ and ending at $(n-m, s+m+1)$. Such a path goes $k$ steps right and $s$ steps up, so there are $\binom{s+k}{k}$ choices.
Side Note: Your sum only needs to go from $k=0$ to $k=n-m$, because when $k > n-m$, then you have $\binom{n-k}{m} = 0$ anyways.
A: $\newcommand{\bbx}[1]{\,\bbox[15px,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{\on}[1]{\operatorname{#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}$
$\ds{\bbox[5px,#ffd]{}}$
$\color{red}{\Large\tt An\ Alternative\color{black}{:}}$
\begin{align}
& \color{#44f}{\sum_{k = 0}^{n}{s + k \choose k}
{n - k \choose m}} =
\bracks{z^{n}}\sum_{\ell = 0}^{\infty}z^{\ell}
\sum_{k = 0}^{\ell}{s + k \choose k}
{\ell - k \choose m}
\\[5mm] = & \
\bracks{z^{n}}\sum_{k = 0}^{\infty}{s + k \choose k}
\sum_{\ell = k}^{\infty}z^{\ell}{\ell - k\choose m}
\\[5mm] = &
\bracks{z^{n}}\sum_{k = 0}^{\infty}
{s + k \choose k}z^{k}
\sum_{\ell = 0}^{\infty}{\ell \choose m}z^{\ell}
\\[5mm] = & \
\bracks{z^{n}}\sum_{k = 0}^{\infty}
{s + k \choose k}z^{k}
\sum_{\ell = m}^{\infty}{\ell \choose m}z^{\ell}
\\[5mm] = & \
\bracks{z^{n - m}}\sum_{k = 0}^{\infty}
{s + k \choose k}z^{k}
\sum_{\ell = 0}^{\infty}{\ell + m \choose m}
z^{\ell}
\\[5mm] = & \
\bracks{z^{n - m}}\sum_{k = 0}^{\infty}
{s + k \choose k}z^{k}
\sum_{\ell = 0}^{\infty}{m + \ell \choose \ell}
z^{\ell}
\end{align}

Note that,
\begin{align}
& \sum_{j = 0}^{\infty}{p + j \choose j}z^{j} =
\sum_{j = 0}^{\infty}\bracks{{-p - 1 \choose j}
\pars{-1}^{j}}z^{j} = \pars{1 - z}^{-p - 1}
\end{align}

Therefore,
\begin{align}
& \color{#44f}{\sum_{k = 0}^{n}{s + k \choose k}
{n - k \choose m}} =
\bracks{z^{n - m}}
\pars{1 - z}^{-s - 1}\,\,\pars{1 - z}^{-m - 1}
\\[5mm] = & \
\bracks{z^{n - m}}\pars{1 - z}^{-s - m - 2}\,\,\, =
{-s - m - 2 \choose n - m}\pars{-1}^{n - m}
\\[5mm] = & \
\bracks{{s + n + 1 \choose n - m}\pars{-1}^{n - m}}
\pars{-1}^{n - m}
\\[5mm] = & \
\bbx{\color{#44f}{s + n + 1 \choose s + m + 1}}
\\ &
\end{align}
