Prove the identity: $\displaystyle\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$
It looks a bit similar to the "no gets their own hat back" problem or inclusion exclusion or non distinct balls in bins.
Trying to find a combinatorial solution seems like impossible because of the alternating sum (how can we explain inclusion exclusion?).
Trying to expand the RHS doesn't help nor using any of the simple identities I know of (like Pascal's).
Any hints or directions please?
Note: no integrals, no generating functions nor use of other identities without proving them.
Edit: I think I got it:
LHS:
n non distinct balls to r bins such that every bin has at least one ball, spread 1 ball to each bin, we're left with n-r balls to r bins.
RHS:
General case: $\binom {n+r-1}{r-1}$
complement: at least one bin is empty; 1 bin is empty, choose that bin $\binom r 1$ and spread the balls: $\binom{n+r-1-1}{r-1-1}$, do this up to r empty bins.
Since we have many over counting, we'll apply the inclusion exclusion principle and we got what we desired.
Best Answer
$$\begin{align} \sum_{k=0}^r(-1)^k\binom rk\binom{n+r-k-1}{r-k-1} &=\sum_{k=0}^r(-1)^k\binom rk\binom{-n-1}{r-k-1}(-1)^{r-k-1}&&(1)\\ &=(-1)^{r-1}\sum_{k=0}^r\binom rk\binom{-n-1}{r-1-k}\\ &=(_1)^{r-1}\binom{r-n-1}{r-1}&&(2)\\ &=(-1)^{r-1}\binom{n-1}{r-1}(-1)^{r-1}&&(3)\\ &=\binom{n-1}{r-1}\qquad\blacksquare \end{align}$$
(1): using Upper Negation
(2): using Vandermonde Identity
(3): using Upper Negation
__
$\color{gray}{\text{Proof of Upper Negation}}$ $$\color{gray}{\begin{align}\\ \binom ab&=\frac{a^{\underline{b}}}{b!} =\frac{a(a-1)(a-2)\cdots(a-b+1)}{b!}\\ &=(-1)^b \frac{[-a][-(a-1)][-(a-2)]\cdots[-(a-b+1)]}{b!}\\ &=(-1)^b \frac{(b-1-a)\cdots(2-a)(1-a)(-a)}{b!}\\ &=(-1)^b \binom{b-a-1}b\end{align}}$$
$\color{gray}{\text{Proof of Vandermonde Identity}}$ $$\color{gray}{\begin{align}\\ \sum_{i=0}^a\binom ai x^i\sum_{j=0}^b\binom bjx^j &=(1+x)^a(1+x)^b=(1+x)^{a+b}\\ [x^n]: \sum_{i+j=n}\binom ai\binom bj &=\underbrace{\sum_{i=0}^n \binom ai\binom b{n-i}=\binom{a+b}n}_{\text{Vandermonde Identity}} \end{align}}$$