How to construct a block-walking argument proof for $\sum_{k=0}^l {l-k \choose m} {q+k \choose n} = {l+q+1 \choose m+n+1}$?

Question

While reading Concrete Math by Knuth and attempting to construct a block-walking argument proof for the equation (5.26) in Table.169, it seems the target of the path is off by one block and stops at ${l+q\choose m+n}$ instead of ${l+q+1\choose m+n+1}$, can anyone shed some light on the possible mistake that caused the difference?

Answer 1

The number of paths from $(0,0)$ to $(m+1+n,l-m+q-n)$ is \begin{align*} \binom{(m+1+n)+(l-m+q-n)}{m+1+n}=\binom{l+q+1}{m+n+1} \end{align*} since the length of each path is $(m+1+n)+(l-m+q-n)=l+q+1$ and we have to select $m+1+n$ $(1,0)$-steps in $x$-direction, leaving $l-m+q-n$ $(0,1)$-steps in $y$-direction.

Now we fix a vertical line going through $(m,0)$. Each path from $(0,0)$ to $(m+1+n,l-m+q-n)$ will cross the line at some point $(m,l-m-k)$ with $0\leq k\leq l-m$.

We can so partition all valid paths by taking paths crossing the line at a specific height $l-m-k$.

The number of paths from $(0,0)$ to $(m+1+n,l-m+q-n)$ passing $(m,l-m-k)$ is the number of paths from $(0,0)$ to $(m,l-m-k)$ times the number of paths from $(m,l-m-k)$ to $(m+1+n,l-m+q-n)$.

Note that from $(m,l-m-k)$ we do horizontal step $(1,0)$ to $(m+1,l-m-k)$, since the vertical step from $(m,l-m-k)$ to $(m,l-m-k+1)$ is already contained when considering all paths from $(0,0)$ to $(m,l-m-k+1)$.

• The number of paths from $(0,0)$ to $(m,l-m-k)$ is $$\binom{l-k}{m}$$

• The number of paths from $(m,l-m-k)$ to $(m+1,l-m-k)$ is $1$

• The number of paths from $(m+1,l-m-k)$ to $(m+1+n,l-m+q-n)$ is $$\binom{((m+1+n)-(m+1))+((l-m+q-n)-(l-m-k))}{(m+1+n)-(m+1)}=\binom{q+k}{n}$$

• The number of paths from $(0,0)$ to $(m+1+n,l-m+q-n)$ passing $(m,l-m-k)$ and $(m+1,l-m-k)$ is $$\binom{l-k}{m}\binom{q+k}{n}$$

Since $k$ may vary from $0$ to $l-m$ we finally get the Chu-Vandermonde Identity in the form

\begin{align*} \color{blue}{\sum_{k=0}^{l-m}\binom{l-k}{m}\binom{q+k}{n}=\binom{l+q+1}{m+n+1}} \end{align*}