Calculate binomial sum

Question

I have problem with the following sum for $n \ge k \ge 0$: $$\sum_{i=0}^k (-1)^i i \binom{n}{i} \binom{n}{k-i}$$

I've tried to use $i\binom{n}{i} = n\binom{n-1}{i-1}$ which give me the form $$n\sum_{i=1}^k (-1)^i \binom{n-1}{n-i} \binom{n}{k-i}$$

and here I stuck.

Answer 1

We start with OPs second form omitting the factor $n$. It is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k}\tag{1} \end{align*}

We obtain for $1\leq k\leq n:$ \begin{align*} \color{blue}{\sum_{i=1}^k}&\color{blue}{(-1)^{i}\binom{n-1}{n-i}\binom{n}{k-i}}\\ &=\sum_{i=0}^{k-1}(-1)^{i+1}\binom{n-1}{i}\binom{n}{k-1-i}\tag{2}\\ &=\sum_{i=0}^\infty(-1)^{i+1}[z^{k-1-i}](1+z)^n[u^i](1+u)^{n-1}\tag{3}\\ &=-[z^{k-1}](1+z)^n\sum_{i=0}^\infty(-z)^i[u^i](1+u)^{n-1}\tag{4}\\ &=-[z^{k-1}](1+z)^n(1-z)^{n-1}\tag{5}\\ &=-([z^{k-1}]+[z^{k-2}])(1-z^2)^{n-1}\tag{6}\\ &=\left\{\begin{array}{rc} \color{blue}{(-1)^{\frac{k}{2}}\binom{n-1}{k/2-1}}&\qquad\color{blue}{ k\equiv 0(2)}\\ \color{blue}{(-1)^{\frac{k+1}{2}}\binom{n-1}{(k-1)/2}}&\qquad \color{blue}{k\equiv 1(2)} \end{array}\right.\tag{7} \end{align*}

Comment:

• In (2) we shift the index $i$ to start with $i=0$ and use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (3) we apply the coefficient of operator twice. We also extend the upper range of the series to $\infty$ without changing anything since we are adding zeros only.

• In (4) we do some rearrangements and use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (5) we use the substitution rule of the coefficient of operator with $u=-z$ \begin{align*} A(z)=\sum_{i=0}^\infty a_iz^i=\sum_{i=0}^\infty z^k[u^i]A(u) \end{align*}

• In (6) we use the linearity of the coefficient of operator again to swallow a factor $(1+z)$.

• In (7) we select the coefficient of $[z^{k-2}]$ resp. $[z^{k-1}]$ according to even and odd $k$.

Answer 2

Observe that $$ \begin{align} \sum_{i=0}^k (-1)^i i \binom{n}{i} \binom{n}{k-i}&=[x^k]\left[ -nx(1-x)^{n-1}\times(1+x)^n \right]\\ &=[x^{k-1}]\left[\frac{-n}{1-x}(1-x^2)^{n}\right]\\ &=-\sum_{m=0,\, \text{even}}^{k-1}n\binom{n}{m/2}(-1)^{m/2} \end{align} $$

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[#ffd,10px]{\ds{\sum_{i = 0}^{k}\pars{-1}^{i}\, i{n \choose i}{n \choose k-i}}} \\[5mm] = &\ \sum_{i = 0}^{\color{red}{\large\infty}}\pars{-1}^{i}\, i{n \choose i}\bracks{z^{k - i}}\pars{1 + z}^{n}\qquad\qquad \pars{\begin{array}{l} \mbox{Note that}\ \ds{{n \choose k - i}_{\ i\ >\ k} = 0} \end{array}} \\[5mm] = &\ \bracks{z^{k}}\pars{1 + z}^{n} \sum_{i = 0}^{\infty}\pars{-z}^{i}\, i{n \choose i} = \bracks{z^{k}}\pars{1 + z}^{n}\ \bracks{z\,\partiald{}{z}\sum_{i = 0}^{\infty}{n \choose i}\pars{-z}^{i}} \\[5mm] = &\ \bracks{z^{k - 1}}\pars{1 + z}^{n}\,\partiald{\pars{1 - z}^{n}}{z} = -n\bracks{z^{k - 1}}\pars{1 + z}^{n}\pars{1 - z}^{n - 1} \\[5mm] = & -n\bracks{z^{k - 1}}\pars{1 + z}\pars{1 - z^{2}}^{n - 1} = -n\bracks{z^{k - 1}}\pars{1 - z^{2}}^{n - 1} - n\bracks{z^{k - 2}}\pars{1 - z^{2}}^{n - 1} \\[5mm] = &\ \bbx{\left\{\begin{array}{lcl} \ds{-n{n - 1 \choose \bracks{k - 1}/2}\pars{-1}^{\pars{k - 1}/2}} & \mbox{if} & \ds{k}\ \mbox{is}\ odd \\[3mm] \ds{-n{n - 1 \choose k/2 - 1}\pars{-1}^{k/2 - 1}} & \mbox{if} & \ds{k}\ \mbox{is}\ even \end{array}\right.} \\ & \end{align}