# How to prove $\sum\limits_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$

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!

• I think it would be convenient if you please elaborate on the assignment of the variables. Is i is of complex number? – Aneek Sep 4 '15 at 15:51
• oh ,no.i is also natural number as n,k. – smallsmallice Sep 5 '15 at 6:41
• oh I see. Thanks! – 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.
• 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. – darij grinberg Sep 5 '16 at 17:45