4
$\begingroup$

How to deal with combinatoric interpretation (or just solving it in algebraic way) when we have $(-1)^i$ factor in our sum?
Example task:
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$
$\endgroup$
  • 1
    $\begingroup$ $(-1)^i$ could very much point to the inclusion-exclusion principle. Did you learn about it? $\endgroup$ – Theorem Apr 6 at 16:35
  • $\begingroup$ I am not sure about that in this case - yes I have learned about that but how it can be used there @Theorem? $\endgroup$ – VirtualUser Apr 6 at 16:36
  • $\begingroup$ 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? $\endgroup$ – Theorem Apr 6 at 16:41
  • $\begingroup$ 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" $\endgroup$ – VirtualUser Apr 6 at 16:44
  • $\begingroup$ 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}$. $\endgroup$ – darij grinberg Apr 6 at 16:53
2
$\begingroup$

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, \begin{equation} \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} \end{equation} 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, \begin{equation} k\dbinom{x}{k}=x\dbinom{x-1}{k-1}\qquad\text{as polynomials in } \mathbb{Q}\left[ x\right] . \end{equation}

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, \begin{equation} \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} \end{equation} 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, \begin{equation} \dbinom{u}{v}=\dbinom{u-1}{v-1}+\dbinom{u-1}{v}, \label{darij1.pf.t1.1} \tag{2} \end{equation} 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 \begin{equation} \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} \end{equation}

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 \begin{equation} \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} \end{equation} 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 \begin{equation} \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} \end{equation}

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 \begin{equation} \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}. \end{equation} This proves Theorem 1. $\blacksquare$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $ $\endgroup$ – VirtualUser Apr 6 at 17:36
  • $\begingroup$ 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.$ $\endgroup$ – Marko Riedel Apr 6 at 17:54
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg Apr 7 at 19:28

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.