-3
$\begingroup$

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

$\endgroup$
2

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ this topic is really hard for me , can u maybe add a draw ? and mark on the draw what every varibale is pointing to please please $\endgroup$
    – Maya Cohen
    Aug 10, 2021 at 6:00
  • $\begingroup$ or if possible contact on mail or zoom ? dolev146@gmail.com $\endgroup$
    – Maya Cohen
    Aug 10, 2021 at 6:01
  • $\begingroup$ well, would you please at first explain why are you interested in having a combinatorial proof of this identity? $\endgroup$ Aug 11, 2021 at 3:43

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