Prove binomial identity $\sum^n_{i = 0} \binom i k = \binom{n+1} {k+1}$ by counting the lattice paths

Question

I encounter a problem where we need to prove the identity $\sum\limits^n_{i = 0} \binom {i} {k} = \binom{n+1} {k+1}$ by counting the lattice paths. I just can't find a way to do it.

Any help would be appreciated!

Answer 1

We can interpret $\binom{n+1}{k+1}$ as number of lattice paths of length $n+1$ containing $k+1$ horizontal $(1,0)$-steps and $n-k$ vertical $(0,1)$-steps.

This is valid because there are $\binom{n+1}{k+1}$ choices to select $k+1$ steps in horizontal direction leaving the remaining $n-k$ steps for the vertical direction.

$$ $$                      $$ $$ Let's consider all paths from $(0,0)$ to $(k+1,n-k)$. We know there are $\binom{n+1}{k+1}$ different paths.

On the other hand each of these paths has to cross the vertical line going through $(k,0)$. The crossing points are $(k,0), (k,1), \ldots, (k,n-k)$. For each path we take as crossing point the node $(k,y)$ which belongs to the path and which has maximum $y$.

This way we partition the set of lattice paths into sets containing $\binom{i}{k}$ elements with $k\leq i \leq n$ establishing the identity

\begin{align*} \sum_{i=0}^n\binom{i}{k}=\binom{n+1}{k+1}\qquad\quad n\geq 0 \end{align*}