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

Question

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?

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

Answer 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.

Answer 3

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

Answer 4

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