# Simplify the sum $\sum_{i=0}^{k}(-1)^i i \binom{n}{i} \binom{n}{k-i}$

How to deal with combinatoric interpretation (or just solving it in algebraic way) when we have $$(-1)^i$$ factor in our sum?
Simplify the sum: $$\sum_{i=0}^{k}(-1)^i i \binom{n}{i} \binom{n}{k-i} \text{ for } 0\le k \le n$$

For task without $$(-1)^i$$ $$\sum_{i=0}^{k} i \binom{n}{i} \binom{n}{k-i} = n \binom{2 n-1}{k-1}$$ I can write that interpretation:

• I have $$n$$ rabbits and $$k$$ slots
• Each rabbit can be in both slot of first type and second type
• slots of first type + second type = $$k$$
• Lets double rabbits
• I choose one rabbit as an king and it will be also a rabbit to slot of first type
• so I need to choose $$2n-1$$ rabbit for $$k-1$$ slots
But I don't know how to deal with $$(-1)^i$$
• $(-1)^i$ could very much point to the inclusion-exclusion principle. Did you learn about it? – Theorem Apr 6 at 16:35
• I am not sure about that in this case - yes I have learned about that but how it can be used there @Theorem? – VirtualUser Apr 6 at 16:36
• That might be because this sum doesn't have a nice closed form? In most cases $(-1)^i$ in combinatoric problems is a definite inclusion-exclusion. Do you have context to this problem? – Theorem Apr 6 at 16:41
• No, I have taken that problem from old exam from my faculty. I checked in wolfram and it claim that the result is $-n \binom{n}{k-1} \, _2F_1(1-k,1-n;-k+n+2;-1)$ but I don't know what is it (checked on wiki that is en.wikipedia.org/wiki/Hypergeometric_function but I haven't got that on my lecture) and how I can get this. The task was just "simplify the sum" – VirtualUser Apr 6 at 16:44
• I can show that the answer is $\dfrac{k}{2} \left(-1\right)^{k/2} \dbinom{n}{k/2}$ when $k$ is even. Interestingly, the answer for $k$ odd seems to be $\dfrac{k+1}{2} \left(-1\right)^{\left(k+1\right)/2} \dbinom{n}{\left(k+1\right)/2}$. – darij grinberg Apr 6 at 16:53

This is a really neat exercise. Here is the answer:

Theorem 1. Let $$n\in\mathbb{N}$$. (Here, as always, $$\mathbb{N}=\left\{ 0,1,2,\ldots\right\}$$.) Let $$m=\left\lfloor \left( n+1\right) /2\right\rfloor$$. Then, $$$$\sum\limits_{k=0}^{n}\left( -1\right) ^{k}k\dbinom{x}{k}\dbinom{x}{n-k}=m\left( -1\right) ^{m}\dbinom{x}{m}$$$$ as polynomials in $$\mathbb{Q}\left[ x\right]$$.

Note that my $$x$$, $$n$$ and $$k$$ are your $$n$$, $$k$$ and $$i$$ (sorry for this -- I am taking the lazy route and adapting your notations to mine), and I have extended the domains for $$x$$ (promoted from a lowly integer to a polynomial indeterminate) and $$n$$ (now any nonnegative integer).

The proof will rely on the following two facts:

Lemma 2. Let $$k$$ be a positive integer. Then, $$$$k\dbinom{x}{k}=x\dbinom{x-1}{k-1}\qquad\text{as polynomials in } \mathbb{Q}\left[ x\right] .$$$$

Proof of Lemma 2. This is usually stated in the equivalent form $$\dbinom {x}{k}=\dfrac{x}{k}\dbinom{x-1}{k-1}$$; in this form it is:

You will have likely proven it by the time you have found it in these sources. Note that this identity is the key to algebraic proofs of various identities with "$$k\dbinom{x}{k}$$"s in them -- such as $$\sum\limits_{k=0}^{n}k\dbinom{n}{k}=n2^{n-1}$$ and $$\sum\limits_{k=0}^{n}\left( -1\right) ^{k}k\dbinom{n}{k}= \begin{cases} -1, & \text{if }n=1;\\ 0, & \text{if }n\neq1 \end{cases}$$ for all $$n\in\mathbb{N}$$. $$\blacksquare$$

Lemma 3. Let $$n\in\mathbb{N}$$. Then, $$$$\sum\limits_{k=0}^{n}\left( -1\right) ^{k}\dbinom{x}{k}\dbinom{x}{n-k}= \begin{cases} \left( -1\right) ^{n/2}\dbinom{x}{n/2}, & \text{if }n\text{ is even};\\ 0, & \text{if }n\text{ is odd} \end{cases} \label{darij1.eq.l3.eq} \tag{1}$$$$ as polynomials in $$\mathbb{Q}\left[ x\right]$$.

Proof of Lemma 3. This is Exercise 3.22 in my Notes on the combinatorial fundamentals of algebra, version of 10 January 2019. Alternatively, if $$x$$ is specialized to a nonnegative integer, you can use Mike Spivey's argument at Alternating sum of squares of binomial coefficients (which is stated for the particular case $$n=x$$, but can easily be adapted to the general case -- see my comment under his post) to prove \eqref{darij1.eq.l3.eq} combinatorially; then, use the "polynomial identity trick" to un-specialize $$x$$. You can probably find lots of other approaches on math.stackexchange. Either way, Lemma 3 is proven. $$\blacksquare$$

Now, we can prove Theorem 1:

Proof of Theorem 1. It is easy to prove Theorem 1 in the case when $$n=0$$. (Indeed, in this case, both sides of the equality in question equal $$0$$, since they are products in which one of the factors is $$0$$.) Thus, for the rest of this proof, we WLOG assume that $$n\neq0$$. Hence, $$n>0$$. Thus, $$n-1 \in \mathbb{N}$$.

We shall use the convention that $$\dbinom{u}{v}=0$$ whenever $$v\notin \mathbb{N}$$. Thus, the recurrence of the binomial coefficients, $$$$\dbinom{u}{v}=\dbinom{u-1}{v-1}+\dbinom{u-1}{v}, \label{darij1.pf.t1.1} \tag{2}$$$$ holds not only for $$v\in\left\{ 1,2,3,\ldots\right\}$$ but for all $$v\in\mathbb{Z}$$.

Lemma 3 (applied to $$n-1$$ instead of $$n$$) yields \begin{align*} \sum\limits_{k=0}^{n-1}\left( -1\right) ^{k}\dbinom{x}{k}\dbinom{x}{\left( n-1\right) -k} & = \begin{cases} \left( -1\right) ^{\left( n-1\right) /2}\dbinom{x}{\left( n-1\right) /2}, & \text{if }n-1\text{ is even};\\ 0, & \text{if }n-1\text{ is odd} \end{cases} \\ & = \begin{cases} 0, & \text{if }n-1\text{ is odd;}\\ \left( -1\right) ^{\left( n-1\right) /2}\dbinom{x}{\left( n-1\right) /2}, & \text{if }n-1\text{ is even} \end{cases} \\ & = \begin{cases} 0, & \text{if }n\text{ is even;}\\ \left( -1\right) ^{\left( n-1\right) /2}\dbinom{x}{\left( n-1\right) /2}, & \text{if }n\text{ is odd} \end{cases} \end{align*} (since $$n-1$$ is odd if and only if $$n$$ is even, and vice versa). Substituting $$x-1$$ for $$x$$ in this equality, we obtain $$$$\sum\limits_{k=0}^{n-1}\left( -1\right) ^{k}\dbinom{x-1}{k}\dbinom{x-1}{\left( n-1\right) -k}= \begin{cases} 0, & \text{if }n\text{ is even;}\\ \left( -1\right) ^{\left( n-1\right) /2}\dbinom{x-1}{\left( n-1\right) /2}, & \text{if }n\text{ is odd.} \end{cases} \label{darij1.pf.t1.n-1} \tag{3}$$$$

If $$n>1$$, then $$n-2\in\mathbb{N}$$. Hence, if $$n>1$$, then Lemma 3 (applied to $$n-2$$ instead of $$n$$) yields \begin{align*} \sum\limits_{k=0}^{n-2}\left( -1\right) ^{k}\dbinom{x}{k}\dbinom{x}{\left( n-2\right) -k} & = \begin{cases} \left( -1\right) ^{\left( n-2\right) /2}\dbinom{x}{\left( n-2\right) /2}, & \text{if }n-2\text{ is even};\\ 0, & \text{if }n-2\text{ is odd} \end{cases} \\ & = \begin{cases} \left( -1\right) ^{\left( n-2\right) /2}\dbinom{x}{\left( n-2\right) /2}, & \text{if }n\text{ is even};\\ 0, & \text{if }n\text{ is odd} \end{cases} \end{align*} (since $$n-2$$ is even if and only if $$n$$ is even, and since $$n-2$$ is odd if and only if $$n$$ is odd). This equality holds not only for $$n>1$$, but also for $$n=1$$ (since both of its sides equal $$0$$ in this case), and thus holds in all cases (since we have $$n\geq1$$). Substituting $$x-1$$ for $$x$$ in this equality, we obtain $$$$\sum\limits_{k=0}^{n-2}\left( -1\right) ^{k}\dbinom{x-1}{k}\dbinom{x-1}{\left( n-2\right) -k}= \begin{cases} \left( -1\right) ^{\left( n-2\right) /2}\dbinom{x-1}{\left( n-2\right) /2}, & \text{if }n\text{ is even};\\ 0, & \text{if }n\text{ is odd.} \end{cases}$$$$ The left hand side of this equality does not change if we replace the summation sign "$$\sum\limits_{k=0}^{n-2}$$" by "$$\sum\limits_{k=0}^{n-1}$$" (because the only new addend that we gain in this way is $$\left( -1\right) ^{n-1}\dbinom{x-1}{n-1} \underbrace{\dbinom{x-1}{\left( n-2\right) -\left(n-1\right)}}_{\substack{ = 0 \\ \text{(since \left(n-2\right)-\left(n-1\right) = -1 \notin \mathbb{N})}}} = 0$$). Hence, this equality becomes $$$$\sum\limits_{k=0}^{n-1}\left( -1\right) ^{k}\dbinom{x-1}{k}\dbinom{x-1}{\left( n-2\right) -k}= \begin{cases} \left( -1\right) ^{\left( n-2\right) /2}\dbinom{x-1}{\left( n-2\right) /2}, & \text{if }n\text{ is even};\\ 0, & \text{if }n\text{ is odd.} \end{cases} \label{darij1.pf.t1.n-2} \tag{4}$$$$

We can split off the addend for $$k=0$$ from the sum $$\sum\limits_{k=0}^{n}\left( -1\right) ^{k}k\dbinom{x}{k}\dbinom{x}{n-k}$$ (since $$n\geq0$$). Thus, we find \begin{align} & \sum\limits_{k=0}^{n}\left( -1\right) ^{k}k\dbinom{x}{k}\dbinom{x}{n-k} \nonumber\\ & =\underbrace{\left( -1\right) ^{0}0\dbinom{x}{0}\dbinom{x}{n-0}}_{=0} +\sum\limits_{k=1}^{n}\left( -1\right) ^{k}k\dbinom{x}{k}\dbinom{x}{n-k} \nonumber\\ & =\sum\limits_{k=1}^{n}\underbrace{\left( -1\right) ^{k}}_{=-\left( -1\right) ^{k-1}}\underbrace{k\dbinom{x}{k}}_{\substack{=x\dbinom{x-1}{k-1}\\\text{(by Lemma 2)}}}\underbrace{\dbinom{x}{n-k}}_{\substack{=\dbinom{x-1} {n-k-1}+\dbinom{x-1}{n-k}\\\text{(by \eqref{darij1.pf.t1.1}, applied} \\ \text{to u = x and v = n-k)}}}\nonumber\\ & =\sum\limits_{k=1}^{n}\left( -\left( -1\right) ^{k-1}\right) x\dbinom{x-1} {k-1}\left( \dbinom{x-1}{n-k-1}+\dbinom{x-1}{n-k}\right) \nonumber\\ & =-x\sum\limits_{k=1}^{n}\left( -1\right) ^{k-1}\dbinom{x-1}{k-1}\left( \dbinom{x-1}{n-k-1}+\dbinom{x-1}{n-k}\right) . \label{darij1.pf.t1.4} \tag{5} \end{align}

Now, \begin{align*} & \sum\limits_{k=1}^{n}\left( -1\right) ^{k-1}\dbinom{x-1}{k-1}\left( \dbinom {x-1}{n-k-1}+\dbinom{x-1}{n-k}\right) \\ & =\sum\limits_{k=0}^{n-1}\left( -1\right) ^{k}\dbinom{x-1}{k}\left( \underbrace{\dbinom{x-1}{n-k-2}}_{=\dbinom{x-1}{\left( n-2\right) -k} }+\underbrace{\dbinom{x-1}{n-k-1}}_{=\dbinom{x-1}{\left( n-1\right) -k} }\right) \\ & \qquad\left( \text{here, we have substituted }k+1\text{ for }k\text{ in the sum}\right) \\ & =\underbrace{\sum\limits_{k=0}^{n-1}\left( -1\right) ^{k}\dbinom{x-1}{k} \dbinom{x-1}{\left( n-2\right) -k}}_{\substack{= \begin{cases} \left( -1\right) ^{\left( n-2\right) /2}\dbinom{x-1}{\left( n-2\right) /2}, & \text{if }n\text{ is even};\\ 0, & \text{if }n\text{ is odd} \end{cases} \\\text{(by \eqref{darij1.pf.t1.n-2})}}}+\underbrace{\sum\limits_{k=0}^{n-1}\left( -1\right) ^{k}\dbinom{x-1}{k}\dbinom{x-1}{\left( n-1\right) -k} }_{\substack{= \begin{cases} 0, & \text{if }n\text{ is even;}\\ \left( -1\right) ^{\left( n-1\right) /2}\dbinom{x-1}{\left( n-1\right) /2}, & \text{if }n\text{ is odd} \end{cases} \\\text{(by \eqref{darij1.pf.t1.n-1})}}}\\ & = \begin{cases} \left( -1\right) ^{\left( n-2\right) /2}\dbinom{x-1}{\left( n-2\right) /2}, & \text{if }n\text{ is even};\\ 0, & \text{if }n\text{ is odd} \end{cases} + \begin{cases} 0, & \text{if }n\text{ is even;}\\ \left( -1\right) ^{\left( n-1\right) /2}\dbinom{x-1}{\left( n-1\right) /2}, & \text{if }n\text{ is odd} \end{cases} \\ & = \begin{cases} \left( -1\right) ^{\left( n-2\right) /2}\dbinom{x-1}{\left( n-2\right) /2}+0, & \text{if }n\text{ is even;}\\ 0+\left( -1\right) ^{\left( n-1\right) /2}\dbinom{x-1}{\left( n-1\right) /2}, & \text{if }n\text{ is odd} \end{cases} \\ & = \begin{cases} \left( -1\right) ^{\left( n-2\right) /2}\dbinom{x-1}{\left( n-2\right) /2}, & \text{if }n\text{ is even;}\\ \left( -1\right) ^{\left( n-1\right) /2}\dbinom{x-1}{\left( n-1\right) /2}, & \text{if }n\text{ is odd} \end{cases} \\ & = \begin{cases} \left( -1\right) ^{\left\lfloor \left( n-1\right) /2\right\rfloor } \dbinom{x-1}{\left\lfloor \left( n-1\right) /2\right\rfloor }, & \text{if }n\text{ is even;}\\ \left( -1\right) ^{\left\lfloor \left( n-1\right) /2\right\rfloor } \dbinom{x-1}{\left\lfloor \left( n-1\right) /2\right\rfloor }, & \text{if }n\text{ is odd} \end{cases} \\ & \qquad\left( \begin{array} [c]{c} \text{since }\left( n-2\right) /2=\left\lfloor \left( n-1\right) /2\right\rfloor \text{ when }n\text{ is even,}\\ \text{and since }\left( n-1\right) /2=\left\lfloor \left( n-1\right) /2\right\rfloor \text{ when }n\text{ is odd} \end{array} \right) \\ & =\left( -1\right) ^{\left\lfloor \left( n-1\right) /2\right\rfloor }\dbinom{x-1}{\left\lfloor \left( n-1\right) /2\right\rfloor }. \end{align*} Thus, \eqref{darij1.pf.t1.4} becomes \begin{align} & \sum\limits_{k=0}^{n}\left( -1\right) ^{k}k\dbinom{x}{k}\dbinom{x}{n-k} \nonumber\\ & =-x\underbrace{\sum\limits_{k=1}^{n}\left( -1\right) ^{k-1}\dbinom{x-1} {k-1}\left( \dbinom{x-1}{n-k-1}+\dbinom{x-1}{n-k}\right) }_{=\left( -1\right) ^{\left\lfloor \left( n-1\right) /2\right\rfloor }\dbinom {x-1}{\left\lfloor \left( n-1\right) /2\right\rfloor }}\nonumber\\ & =-x\left( -1\right) ^{\left\lfloor \left( n-1\right) /2\right\rfloor }\dbinom{x-1}{\left\lfloor \left( n-1\right) /2\right\rfloor } . \label{darij1.pf.t1.7} \tag{6} \end{align}

On the other hand, recall that $$m=\left\lfloor \left( n+1\right) /2\right\rfloor$$, so that $$m-1=\left\lfloor \left( n+1\right) /2\right\rfloor -1=\left\lfloor \underbrace{\left( n+1\right) /2-1} _{=\left( n-1\right) /2}\right\rfloor =\left\lfloor \left( n-1\right) /2\right\rfloor$$. Also, $$m=\left\lfloor \left( n+1\right) /2\right\rfloor \geq1$$ (since $$n\geq1$$ and thus $$\left( n+1\right) /2\geq1$$). Hence, $$m$$ is a positive integer; thus, Lemma 2 (applied to $$k=m$$) yields $$m\dbinom{x} {m}=x\dbinom{x-1}{m-1}$$. Now, \begin{align*} m\left( -1\right) ^{m}\dbinom{x}{m} & =\underbrace{\left( -1\right) ^{m} }_{=-\left( -1\right) ^{m-1}}\underbrace{m\dbinom{x}{m}}_{=x\dbinom {x-1}{m-1}}=-\left( -1\right) ^{m-1}x\dbinom{x-1}{m-1}\\ & =-x\left( -1\right) ^{m-1}\dbinom{x-1}{m-1}=-x\left( -1\right) ^{\left\lfloor \left( n-1\right) /2\right\rfloor }\dbinom{x-1}{\left\lfloor \left( n-1\right) /2\right\rfloor } \end{align*} (since $$m-1=\left\lfloor \left( n-1\right) /2\right\rfloor$$). Comparing this with \eqref{darij1.pf.t1.7}, we obtain $$$$\sum\limits_{k=0}^{n}\left( -1\right) ^{k}k\dbinom{x}{k}\dbinom{x}{n-k}=m\left( -1\right) ^{m}\dbinom{x}{m}.$$$$ This proves Theorem 1. $$\blacksquare$$

Starting from

$$\sum_{q=0}^k (-1)^q q {n\choose q} {n\choose k-q}$$

we have

$$\sum_{q=1}^k (-1)^q q {n\choose q} {n\choose k-q} = n \sum_{q=1}^k (-1)^q {n-1\choose q-1} {n\choose k-q} \\ = n [z^k] (1+z)^n \sum_{q=1}^k (-1)^q {n-1\choose q-1} z^q \\ = - n [z^{k-1}] (1+z)^n \sum_{q=1}^k (-1)^{q-1} {n-1\choose q-1} z^{q-1}.$$

Now if $$q\gt k$$ then there is no contribution to the coefficient extractor:

$$- n [z^{k-1}] (1+z)^n \sum_{q\ge 1} (-1)^{q-1} {n-1\choose q-1} z^{q-1} \\ = - n [z^{k-1}] (1+z)^n (1-z)^{n-1} = - n [z^{k-1}] (1+z) (1-z^2)^{n-1} \\ = - n [z^{k-1}] (1-z^2)^{n-1} - n [z^{k-2}] (1-z^2)^{n-1}.$$

If $$k$$ is odd this yields

$$-n (-1)^{(k-1)/2} {n-1\choose (k-1)/2}$$

and if it is even

$$-n (-1)^{(k-2)/2} {n-1\choose (k-2)/2}.$$

Join these to obtain

$$\bbox[5px,border:2px solid #00A000]{ (-1)^{1+\lfloor (k-1)/2 \rfloor} \times n \times {n-1\choose \lfloor (k-1)/2 \rfloor}.}$$

• can you explain how you do this equality? $n \sum_{q=1}^k (-1)^q {n-1\choose q-1} {n\choose k-q} = n [z^k] (1+z)^n \sum_{q=1}^k (-1)^q {n-1\choose q-1} z^q$ – VirtualUser Apr 6 at 17:36
• This is coefficient extraction for formal power series applied to ${n\choose k-q} = [z^{k-q}] (1+z)^n = [z^k] z^q (1+z)^n.$ – Marko Riedel Apr 6 at 17:54

Darij Grinberg's answer cited a very nice combinatorial proof which I reproduce here for completeness.

Let $$[n]=\{1,2,\dots,n\}$$. We provide a combinatorial interpretation for the form $$\sum_i (-1)^in\binom{n-1}{i-1}\binom{n}{k-i}$$ This is a signed count of ordered triples $$(x,A,B)$$, where $$x\in [n], A\subseteq [n]\setminus \{x\},B\subseteq [n]$$, and $$|A|+|B|=k-1$$. A triple is counted positively if $$|A|$$ is odd, and negatively otherwise.

Given such a triple $$(x,A,B)$$, we define its partner $$f(x,A,B)$$ as follows. Find the largest element of $$(A\setminus B)\cup (B\setminus (A\cup \{x\}))$$, and move it to the other set. If this set is empty, we leave $$f$$ undefined.

You can check that $$f(f(x,A,B))=(x,A,B)$$ whenever $$f$$ is defined, so that this is a well defined pairing operation. Furthermore, since $$(x,A,B)$$ and $$f(x,A,B)$$ have opposite signs, they cancel out each other in the summation, so they can be ignored.

Therefore, the only triples which contribute to the count are those for which $$f$$ is undefined. The only triples for which $$f$$ is undefined are those of the form $$(x,A,A)$$ and $$(x,A,A\cup \{x\})$$. Only one of these forms is possible, depending on the parity of $$k$$, and you can check that in either case the number of triples is $$n\binom{n-1}{\lfloor(k-1)/2\rfloor}$$ and each exceptional triple has sign $$(-1)^{\lfloor(k-1)/2\rfloor + 1}$$.

• Nice proof! Your set $(A\setminus B)\cup (B\setminus (A\cup \{x\}))$ can also be written as the symmetric difference $A \triangle \left(B \setminus \left\{x\right\}\right)$. I'm saying this because it makes it a lot easier to see why your $f$ is an involution. – darij grinberg Apr 7 at 19:28