4
$\begingroup$

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 enter image description here

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!

$\endgroup$

2 Answers 2

4
$\begingroup$

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

                                    enter image description here

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .