Prove identity $\sum^n_{k = 0} \binom {r+k} {r} = \binom{r+n+1} {r+1}$ using lattice paths

Question

I am trying to prove the following identity $\sum^n_{k = 0} \binom {r+k} {r} = \binom{r+n+1} {r+1}$ by using lattice paths. My first approach was to draw the following scheme:

Sketch indicating paths

I'm aware that $\binom{r+n+1} {r+1}$ counts the number of shortest paths from $(0,0)$ to $(n, r+1)$ and I also know that $\binom{r+k} {k}$ counts paths from the origin to $(k,r)$ where $0 \le k\le n$.

I think I can deal with paths like the blue one shown in the Sketch, because it intercepts the green line on only one point. But I'm stuck when it comes to paths like the red one, I do not know how to count them in a proper way.

Any insight would be very appreciated!

Answer 1

A shortest path consists of $n$ steps to the right and $r+1$ steps upward. There are totally $n+r+1$ steps and the number of shortest path is $n+r+1 \choose r+1$ (choosing $r+1$ steps to go upward.

Suppose that in a shortest path, the first $k$ ($k=0,1,2\dots, n$) steps are to the right (and the $(k+1)$st step goes upward). The number of such a shortest path is corresponding to a shortest path without constraint starting from the point $(k, 1)$. So the count is $k+r \choose r$.

Therefore, $\displaystyle \sum_{k=0}^n {k+r \choose r}= {n+r+1 \choose r+1}$.

Answer 2

We consider the lattice paths of length $r+1+n$ from $(0,0)$ to $(r+1,n)$ consisting of $(1,0)$-steps and $(0,1)$-steps only. The number of these paths is $$\binom{r+1+n}{r+1}$$ since we have to choose precisely $r+1$ $(1,0)$-steps out of $r+1+n$ steps.

We fix a vertical line going through $(r,0)$. Each path from $(0,0)$ to $(r+1,n)$ will cross the line at some point $(r,k)$ with $0\leq k\leq n$ and the number of these paths is $\binom{r+k}{r}$.

                                    

We can so partition all valid paths by taking paths crossing the line at a specific height $k$, followed by a horizontal step to $(r+1,k)$ and $n-k$ vertical steps to $(r+1,n)$.

We conclude \begin{align*} \sum_{k=0}^n\binom{r+k}{r}=\binom{r+1+n}{r+1} \end{align*} and the claim follows.