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

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:

• the "absorption identity" (5.5) in Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Second Edition, Addison-Wesley 1994.

• Proposition 3 in https://math.stackexchange.com/a/2974977/ (except that I am calling the indeterminate $y$ rather than $x$ there);

• Proposition 3.26 (e) in my Notes on the combinatorial fundamentals of algebra, version of 10 January 2019.

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$