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

Solution 1:

Hint 1: To calculate $\sum_{k=0}^n (-1)^k \binom{n}{k}^2$, by using the identity $(1-x^2)^n=(1-x)^n(1+x)^n$, show that for each non-negative integer $m\le n$, $$\sum_{k=0}^{2m} (-1)^k \binom{n}{k} \binom{n}{2m-k}=(-1)^m \binom{n}{m},$$ and $$\sum_{k=0}^{2m+1} (-1)^k \binom{n}{k} \binom{n}{2m+1-k}=0.$$ Then consider the two different cases when $n$ is even and when $n$ is odd.

Hint 2: To calculate $\sum_{k=0}^n k \binom{n}{k}^2$, consider a class of $n$ boys and $n$ girls then try to select $n$ guys with a boy as their leader.

Another way to calculate these summations is to use the generating functions.

$A(z)=(1+z)^n$ is the generating function for $a_m=\binom{n}{m}$, and $B(z)=zA'(z)=nz(1+z)^{n-1}$ is the generating function for $b_m=ma_m=m\binom{n}{m}$. Therefore $C(z)=B(z)A(z)=nz(1+z)^{2n-1}$ is the generating function for the convolution $c_m=\sum_{k=0}^m{b_k a_{m-k}}=\sum_{k=0}^m{k\binom{n}{k}\binom{n}{m-k}}$, but $$\begin{align} C(z) & = nz(1+z)^{2n-1} \\ & = nz\sum_{m=0}^{2n-1}{\binom{2n-1}{m} z^m} \\ & = \sum_{m=1}^{2n}{n\binom{2n-1}{m-1} z^m}. \\ \end{align}$$ Thus $$\sum_{k=0}^m{k\binom{n}{k}\binom{n}{m-k}}=c_m=n\binom{2n-1}{m-1},$$ now if m=n then $$n\binom{2n-1}{n-1}=\sum_{k=0}^n{k\binom{n}{k}\binom{n}{n-k}}=\sum_{k=0}^n{k\binom{n}{k}^2}.$$

Also if you can calculate $\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i}$, then you know that $$\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}.$$ Now if we use the identity $k\binom{n}{k}=n\binom{n-1}{k-1}$, then we have $$\begin{align} \sum_{k=0}^n k \binom{n}{k}^2 & =\sum_{k=0}^n k \binom{n}{k} \binom{n}{k} \\ & = n \sum_{k=0}^n \binom{n-1}{k-1} \binom{n}{k} \\ & = n \sum_{k=0}^n \binom{n-1}{n-k} \binom{n}{k} \\ & = n \binom{(n-1)+n}{n} \\ & = n \binom{2n-1}{n-1}. \end{align}$$

Solution 2:

Using the Lemma from this answer, we get $$ \begin{align} \sum_{k=0}^nk\binom{n}{k}^2 &=\sum_{k=0}^n\binom{k}{1}\binom{n}{k}^2\\ &=\binom{n}{1}\binom{2n-1}{n}\\ &=\bbox[5px,border:2px solid #C00000]{n\binom{2n-1}{n}}\\ &\text{or}\\ &=\binom{2n-1}{1}\binom{2n-2}{n-1}\\ &=\bbox[5px,border:2px solid #C00000]{(2n-1)\binom{2n-2}{n-1}}\tag{1} \end{align} $$

To get the alternating sum, consider the product $$ \begin{align} (1+x)^n(1-x)^n &=\left(\sum_{i=0}^n\binom{n}{i}x^i\right)\left(\sum_{j=0}^n\binom{n}{j}(-1)^jx^j\right)\\ &=\sum_{k=0}^{2n}\sum_{j=0}^k(-1)^jx^k\binom{n}{j}\binom{n}{k-j}\tag{2} \end{align} $$ Note that the coefficient of $x^n$ in $(2)$ is $$ \sum_{j=0}^n(-1)^j\binom{n}{j}\binom{n}{n-j}=\sum_{j=0}^n(-1)^j\binom{n}{j}^2\tag{3} $$ Another way to write the left hand side of $(2)$ is $(1-x^2)^n$. If $n$ is odd, there is no $x^n$ term in $(1-x^2)^n$ since it is an even function. If $n$ is even, the coefficient of $x^n$ is $(-1)^{n/2}\binom{n}{n/2}$. Therefore, $$ \bbox[5px,border:2px solid #C00000]{ \sum_{j=0}^n(-1)^j\binom{n}{j}^2=\left\{\begin{array}{} \displaystyle0&\text{if $n$ is odd}\\ \displaystyle(-1)^{n/2}\binom{n}{n/2}&\text{if $n$ is even} \end{array}\right.}\tag{4} $$

Solution 3:

An alternative approach for what used to be your first identity $\sum\limits_{i=0}^k \binom{i}{n}\binom{k-i}{m}$ is as follows:

For each value of $i$ you want to count the subsets of $1,2,\dots n+1$ containing exactly $n$ elements in $\{1,2,3\dots i\}$ and exactly $m$ elements in $\{i+2,i+3\dots k+1\}$ . So $i+1$ is like a barrier. Given a subset of size $n+m+1$ you can find which is the barrier and you have one of the desired configuration. Then $\sum\limits_{i=0}^k \binom{i}{n}\binom{k-i}{m}$ is $\binom{k+1}{n+m+1}$

What is your first identity right now is called vandermonde's identity.Another way to see it is that you want the subsets of $k$ elements from disjoint sets $A$ and $B$ where the quantity of elements in $A$ goes from $0$ to $k$. Hence you want all of the $k$-subsets of $A\cup B$

For calculating the $\sum\limits_{i=0}^n \binom{n}{i}^2 (-1)^i$ Alex R's comment is good. Although it only works for odd $n$.

The point is that $\binom{n}{i}=\binom{n}{n-i}$ and $i$ and $n-i$ have different parity when $n$ is odd. So they cancel out. so if $n=2k$ you obtain $\sum_{i=0}^{2k+1}\binom{2k+1}{i}^2(-1)^i=0$