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

Solution 1:

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

Solution 2:

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.

Solution 3:

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