Exotic proofs of $\sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$

Question

Let $p,n$ be positive integers.

The following identity $\displaystyle \sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$ may be proved by induction or by successive uses of Pascal's rule (both techniques are demonstrated here).

Question

Is there a combinatorial proof for this identity ? Do you know other proofs ?

Answer 1

First Proof: \begin{align} \sum^{n-1}_{j=0}\binom{p+j}{p} &=\frac{1}{2\pi i}\oint_{|z|=1}\frac{(1+z)^p}{z^{p+1}}\sum^{n-1}_{j=0}(1+z)^j{\rm d}z\\ &=\frac{1}{2\pi i}\oint_{|z|=1}\frac{(1+z)^{n+p}-(1+z)^p}{z^{p+2}}{\rm d}z\\ &=\frac{1}{(p+1)!}\lim_{z \to 0}\frac{{\rm d}^{p+1}}{{\rm d}z^{p+1}}\left[(1+z)^{n+p}-(1+z)^p\right]\\ &=\frac{(n+p)(n+p-1)\cdots(n+1)(n)}{(p+1)!}\\ &=\binom{n+p}{p+1} \end{align} Second Proof: \begin{align} \sum^{n-1}_{j=0}\binom{p+j}{p} &=[x^N]\sum^\infty_{N=0}\sum^{N=n-1}_{j=0}\binom{p+j}{j}x^N\\ &=[x^N]\sum^\infty_{j=0}\binom{p+j}{j}\sum^\infty_{N=j}x^N\\ &=[x^N]\sum^\infty_{j=0}\binom{p+j}{j}\frac{x^j}{1-x}\\ &=[x^{n-1}]\frac{1}{(1-x)^{p+2}}\\ &=\binom{p+2+n-1-1}{n-1}\\ &=\binom{p+n}{p+1} \end{align}

Answer 2

We want to show a bijection from $p+1$-element subsets of $\{0,\dots,p+n-1\}$ to pairs $(j, A)$, where $0 \le j \le n-1$ and $A$ is a $p$-element subset of $\{0,1,\dots,p+j-1\}$. Note that there are exactly $\sum_{j=0}^{n-1} {p+j \choose p}$ such pairs and ${p+n \choose p+1}$ such subsets, so if we prove this bijection, we will also prove the identity.

Take any $p+1$-element subset $B$ of $\{0,\dots,p+n-1\}$. Let $m$ be its biggest element. Then note that it uniquely defines a pair $(m, B\setminus\{m\})$. On the other side, if we have a pair $(j, A)$, then it uniquely defines $A \cup \{j\}$, which is a $p+1$-element subset of $\{0,1,\dots,p+n-1\}$. This proves the identity.

Answer 3

This proof can be viewed as the combinatorial explanation of "successive Pascal's rule".

Suppose we want to choose $p+1$ numbers $a_1<a_2<\cdots<a_{p+1}$ out of $\{1,\dots, p+n\}$. It is clear that $a_{p+1}$ can only be in $\{p+1,p+2,\cdots, p+n\}$. For each value $a_{p+1}=p+j$ in $\{p+1,p+2,\dots,p+n\}$, there are $\binom{p+j-1}{p}$ choices of $a_1<a_2<\cdots<a_p$. Add all the cases one get the required identity.

Answer 4

Here's a combinatorial proof (admittedly, not the simplest way of proving this): we want to double count the ways of choosing $p+1$ elements from a set of $p+n$ elements denoted by $A$. On one hand it is $\binom{p+n}{p+1}$.

An other way of counting is this: Let $P_0\subset A$ be a fixed subset of our original set with $p$ elements, and let $j_0 \in A \setminus P_0$. The number of ways of choosing a subset of $p+1$ elements from $P_0 \bigcup \{j_0 \} $ that contains $j_0$ is of course $\binom{p}{p}=1$.

Now let $P_1 = P_0 \bigcup \{j_0\}$ and choose an element $j_1$ from $A \setminus P_1$. The number of ways of choosing a subset of $p+1$ elements from $P_0 \bigcup \{j_1 \}$ that contains $j_1$ is $\binom{p+1}{p}$.

Continue this procedure until you reach $P_{n-p}=A$. This way you've counted all $p+1$ element subsets$^1$, and each subset is counted at most once$^2$, so this indeed is the number of ways of choosing $p+1$ elements from $A$. Adding up the number of subsets chosen in each step gives the required result.

---

$^1$Let $B$ be a $p+1$ element subset of $A$. It must contain at least one $j_i$, and so there's a nonnegative integer $k$ such that $j_k \in B$ and for all $i>k$, $j_i \notin B$. Then we must have chosen $B$ in the $k+1$-th step of the procedure.

$^2$The subsets chosen in the same step are obviously distinct, and you can't choose the same subsets in steps $j,k$ where $j<k$, since every subset chosen in the $k$-th step has $j_{k-1}$ as an element, while none of the subsets chosen in the earlier steps does.

Answer 5

Here $\Bbb N = \{0,1,2,\dots\}$.

Define

$\tag 1 \Bbb W = \{(n,k) \in \Bbb N \ \times \Bbb N\mid k \le n\}$

Consider any function $g: \Bbb W \to \Bbb N$ satisfying

$\tag 2 g(n,k) = g(n-1,k) + g(n-1,k-1)$

where $(n,k)$ is not on the boundary of the wedge $\Bbb W$.

The following identity can be established using induction

$\tag 3 \displaystyle g(p+n,p+1) = g(p+1,p+1) + \sum_{j=1}^{n-1}g(p+j,p) \text{ where } n \ge 1$

An example of such a function is given by

$\tag 4 g(n,k) = \binom{n}{k}$

So

$\tag 5 \binom{p+n}{p+1} = \binom{p+1}{p+1} + \sum_{j=1}^{n-1}\, \binom{p+j}{p}$

Since

$\quad \binom{p+1}{p+1} + \binom{p}{p}$

we can rewrite $\text{(5)}$ as

$\tag 5 \displaystyle \binom{p+n}{p+1} = \sum_{j=0}^{n-1}\, \binom{p+j}{p}$