Lattice path: proof of $\sum_{k=0}^n{s+k \choose k}{n-k \choose m}={s+n+1 \choose s+m+1}$

Question

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.

Answer 1

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.

Answer 2

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