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*}

A: The RHS counts the ways to select $p+1$ places in a line of $n+1$ places.
The LHS counts the ways to select $p$ places in a line of $k$ places, summed over all values of $k: 0\leq k\leq n$.   (More strictly, $k: p\leq k\leq n$, since there are no ways to do this for $k<p$).
Interpreting $k+1$ as the position of the last, or $(p+1)^{st}$, place, we notice that these both count ways to perform the exact same task.   Ergo they are equivalent.
$$\sum_{k=p}^n \dbinom{k}{p} = \binom{n+1}{p+1}$$
