Exotic proofs of $\sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$ 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 ?
 A: 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}
A: 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.
A: 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.
A: 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. 
A: 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}$
