combinatoric proof $\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$ [closed]

Question

I would like help with combinatorial proof , not algebraic proof . Thank you for your time

$\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$

Answer 1

Denote $[n]=\{1,\ldots,n\}$.

We choose an $i$-subset $A\subset [n]$, then a $k$-multiset $B\subset [n]\setminus A$, and take $(-1)^i$ for each such a choice. Note that if $B$ is fixed, the sum of $(-1)^{|A|}$ over subsets $A\subset [n]\setminus B$ equals to 0 unless $B=[n]$, when the sum equals 1. Therefore we should count $k$-multisets $B$ which cover $[n]$. These are in bijection with $(k-n)$-multisets of $[n]$, there exist exactly ${k-n+(n-1)\choose k-n}={k-1\choose k-n}$ such multisets.