6
$\begingroup$

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?

$\endgroup$

marked as duplicate by Jack D'Aurizio, user230715, Macavity, vonbrand, 6005 Aug 25 '15 at 20:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ In case $p=0$? More than one question mark reads as an insulting tone. @WillJagy $\endgroup$ – Thomas Andrews Aug 25 '15 at 2:37
  • $\begingroup$ @WillJagy I do realize that $\binom kp = 0$ if $k <p$ $(k \in \mathbb{Z})$. I guess it is more elegant to write it that way. And everything is well defined so there is no issues. $\endgroup$ – Miz Aug 25 '15 at 2:40
  • $\begingroup$ @GeorgeSimpson: I disagree with this duplication mark. This question is explicitly asking for a combinatorial proof contrary to the referred question. So, two of three answers of the referred question are to exlude as proper answer for this question. The combinatorial answers here which are quite ok for this question do hardly answer the referred binomial identity. $\endgroup$ – Markus Scheuer Aug 26 '15 at 8:21
  • 1
    $\begingroup$ @MarkusScheuer Looking among linked and related questions it seems that there are several other questions about combinatorial proof of the same identity. For example: 321022, 497413 1332282. If needed, we can discuss this further in chat. $\endgroup$ – Martin Sleziak Aug 29 '15 at 7:59
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.