Q:

Combinatorial Proof for Binomial Identity: $\sum_{k = 0}^n \binom{k}{p} = \binom{n+1}{p+1}$

I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant counting trick we can use to arrive at this identity? 

A:

What do you get when you take a sequence of ones and zeros of length $n+1$  that has $k+1$ ones and remove the rightmost $1$ and everything to its right?
Example: $100100\rightarrow 100$
You get a sequence that has $k$ ones, the length varies between $k$ and $n$ depending on the actual sequence.
In fact this function is a bijection between the sequences of length $n+1$ and $k+1$ ones and the sequences of length $n$ or less and $k$ ones.
This establishes $\binom{n+1}{k+1}=\sum\limits_{j=k}^{n}\binom{j}{k}$

A:

I'd prefer to omit the zero terms and prove
$$
\sum_{k = p}^n \binom{k}{p} = \binom{n+1}{p+1}.
$$
Suppose we have $n+1$ people standing in a line so that we can refer to Person 1, Person 2, ..., Person $n+1$.
The righthand side counts the number of committees of size $p+1$ that can be formed out of these $n+1$ people.
The lefthand side counts the same thing, but it does so in cases.
The first case is that Person $p+1$ is the largest numbered person in the committee. This means we must choose the remaining $p$ committee members from the first $p$ people in line, which can be done in $\binom{p}{p}$ ways.
The second case is that Person $p+2$ is the largest numbered person in the committee. This means we must choose the remaining $p$ committee members from the first $p+1$ people in line, which can be done in $\binom{p+1}{p}$ ways.
Continuing in this way, the last case would be that Person $n+1$ is the largest numbered person in the committee. This means we must choose the remaining $p$ committee members from the first $n$ people in line, which can be done in $\binom{n}{p}$ ways.
Summing over these cases yields the desired identity.

A:

Here is another combinatorial approach using lattice paths. 

We can interpret $\binom{n+1}{p+1}$ as number of lattice paths of length $n+1$ containing $p+1$ horizontal $(1,0)$-steps and $n-p$ vertical $(0,1)$-steps.
This is valid because there are $\binom{n+1}{p+1}$ choices to select $p+1$ steps in horizontal direction leaving the remaining $n-p$ steps for the vertical direction.

$$ $$

Let's consider all paths from $(0,0)$ to $(p+1,n-p)$. We know there are $\binom{n+1}{p+1}$ different paths.
On the other hand each of these paths has to cross the vertical line going through $(p,0)$. The crossing points are $(p,0), (p,1), \ldots, (p,n-p)$. This way we partition the set of lattice paths into sets containing $\binom{k}{p}$ elements with $p\leq k \leq n$ establishing the identity
\begin{align*}
  \sum_{k=0}^n\binom{k}{p}=\binom{n+1}{p+1}\qquad\quad n\geq 0
  \end{align*}

