6
$\begingroup$

$$\text{Find} \ \ \sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$$

I expanded the binomial coefficients within the sum and got $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dots + \binom{n}{n}^2$$ What does this equal to? I think this can help me evaluate the original sum.

$\endgroup$
6
$\begingroup$

First, use $k\binom{n\vphantom{1}}{k}=n\binom{n-1}{k-1}=n\binom{n-1}{n-k}$ $$ \sum_{k=0}^n(-1)^kk\binom{n}{k}^2 =n\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{n-1}{n-k}\tag{1} $$ Next compute a generating function. The sum we want is the coefficient of $x^n$ $$ \begin{align} n\sum_{m,k}(-1)^k\binom{n}{k}\binom{n-1}{m-k}x^m &=n\sum_{m,k}(-1)^k\binom{n}{k}\binom{n-1}{m-k}x^{m-k}x^k\\ &=n\sum_k(-1)^k\binom{n}{k}(1+x)^{n-1}x^k\\ &=n(1+x)^{n-1}(1-x)^n\\ &=n\left(1-x^2\right)^{n-1}(1-x)\tag{2} \end{align} $$ The sum we want is the coefficient of $x^n$ in $(2)$: $$ \begin{align} \sum_{k=0}^n(-1)^kk\binom{n}{k}^2 &=\left\{\begin{array}{} n\binom{n-1}{n/2}(-1)^{n/2}&\quad\text{if $n$ is even}\\[6pt] n\binom{n-1}{(n-1)/2}(-1)^{(n+1)/2}&\quad\text{if $n$ is odd} \end{array}\right.\\[6pt] &=n\binom{n-1}{\lfloor n/2\rfloor}(-1)^{\lceil n/2\rceil}\tag{3} \end{align} $$

$\endgroup$
  • $\begingroup$ This has been verified for $0\le n\le200$. $\endgroup$ – robjohn May 10 '13 at 8:03
3
$\begingroup$

$$\text{ Hint: }\sum^{n}_{k=0}(-1)^k{n\choose k}^2=(-1)^m{2m\choose m},\ m=\frac{n}{2},\ \forall n: 2\mid n$$ $$\text{and}$$ $$\sum^{n}_{k=0}(-1)^k{n\choose k}^2=0,\ \forall n:2\nmid n$$

$\endgroup$
  • $\begingroup$ There should be a K in the sum. $\endgroup$ – please delete me May 10 '13 at 3:44
  • $\begingroup$ Yes I know, I'm just saying that this might help ... $\endgroup$ – user67258 May 10 '13 at 3:47
  • $\begingroup$ Ok, yes, I fixed my answer since its only an AP. Thanks for the help! $\endgroup$ – please delete me May 10 '13 at 3:48
  • $\begingroup$ Following the logic in my answer, this sum is the coefficient of $x^n$ in $\left(1-x^2\right)^n$ (which gives the answer you cite). $\endgroup$ – robjohn May 10 '13 at 13:09
3
$\begingroup$

This can also be done using a basic complex variables technique. Start as in @robjohn's answer. Suppose we seek to evaluate $$\sum_{k=0}^n (-1)^k k {n\choose k}^2 = \sum_{k=1}^n {n\choose k} (-1)^k k {n\choose k} \\= \sum_{k=1}^n {n\choose k} (-1)^k k \frac{n}{k} {n-1\choose k-1} = n \sum_{k=1}^n {n\choose k} (-1)^k {n-1\choose k-1}.$$

Introduce the integral representation $${n-1\choose k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^k} (1+z)^{n-1} \; dz.$$

This gives the following integral for the sum $$\frac{n}{2\pi i} \int_{|z|=\epsilon} \sum_{k=1}^n {n\choose k} (-1)^k \frac{1}{z^k} (1+z)^{n-1} \; dz \\= \frac{n}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \sum_{k=1}^n {n\choose k} (-1)^k \frac{1}{z^k} \; dz \\= \frac{n}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \left(-1 + \left(1-\frac{1}{z}\right)^n \right) \; dz$$

We may drop the $-1$ because it participates in a product that is entire. This leaves $$\frac{n}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{(z-1)^n}{z^n} \; dz \\ = \frac{(-1)^n n}{2\pi i} \int_{|z|=\epsilon} (1-z) (1+z)^{n-1} \frac{(1-z)^{n-1}}{z^n} \; dz \\ = \frac{(-1)^n n}{2\pi i} \int_{|z|=\epsilon} (1-z) \frac{(1-z^2)^{n-1}}{z^n} \; dz.$$

It follows that the value of the sum is given by $$(-1)^n n [z^{n-1}] (1-z) (1-z^2)^{n-1}.$$

For $n$ even the $z$ from $1-z$ participates and for $n$ odd the one participates.

We have for $n$ even the result $$(-1)^n n \times (-1) (-1)^{(n-2)/2} {n-1\choose (n-2)/2} = n \times (-1)^{n/2} {n-1\choose n/2-1} \\= n \times (-1)^{n/2} {n-1\choose n/2}$$ and for $n$ odd $$(-1)^n n \times (-1)^{(n-1)/2} {n-1\choose (n-1)/2} = n \times (-1)^{(n+1)/2} {n-1\choose (n-1)/2}.$$

Joining these two terms we obtain $$n \times (-1)^{\lceil n/2 \rceil} {n-1\choose \lfloor n/2 \rfloor}.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

$\endgroup$

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.