I saw a combinatorial identity when i study linear-algebra, But the author didn't explain how to get it.

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

Who can help me to prove it? Thanks!

  • $\begingroup$ I think it would be convenient if you please elaborate on the assignment of the variables. Is i is of complex number? $\endgroup$ – Aneek Sep 4 '15 at 15:51
  • $\begingroup$ oh ,no.i is also natural number as n,k. $\endgroup$ – smallsmallice Sep 5 '15 at 6:41
  • $\begingroup$ oh I see. Thanks! $\endgroup$ – Aneek Sep 5 '15 at 10:16

You probably want to require $k > 0$, as otherwise your claim is $1 = 0$.

Renaming $k$, $n$ and $i$ as $n$, $x$ and $k$, you get a particular case (the case $x=y$) of the following identity:

$\sum\limits_{k=0}^n \left(-1\right)^k \dbinom{x}{n-k} \dbinom{k+y-1}{k} = \dbinom{x-y}{n}$.

This is, e.g., Proposition 3.32 (d) in my Notes on the combinatorial fundamentals of algebra. (In case of changing numbering, search for " some sample applications of Theorem", or check out the frozen version of 10 January 2019, in which the numbering surely has not shifted.) The main trick to the proof is realizing that $\left(-1\right)^k \dbinom{k+y-1}{k}$ can be rewritten as $\dbinom{-y}{k}$, after which you are left with a particular case of the Vandermonde convolution identity.

  • $\begingroup$ Pretty good book!but seems a little difficult to me ... I' ll try my best to read it ! Thank you very much ! $\endgroup$ – smallsmallice Sep 2 '15 at 12:14
  • $\begingroup$ ok~thanks a lot! $\endgroup$ – smallsmallice Sep 2 '15 at 13:58
  • $\begingroup$ This isn't a book, though it might become one... The proof of Proposition 2.25 is mostly self-contained, relying only on Theorem 2.24 and on some basic identities such as upper negation (Proposition 2.16). If you have trouble with the notations (such as binomial coefficients $\dbinom{m}{n}$ with negative $m$), look them up at the beginning of Chapter 2. $\endgroup$ – darij grinberg Sep 5 '16 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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