6
$\begingroup$

I can calculate $\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i}$ using $(1+x)^{n+m} = (1+x)^n(1+x)^m$.

I would like to calculate the two sums $\sum_{k=0}^n (-1)^k \binom{n}{k}^2$ and $\sum_{k=0}^n k \binom{n}{k}^2$ with the same method.

I don't see what polynomial I have to consider.

For the first one, if i consider $(1-x)^n(1+x)^n=\sum_{k=0}^n \sum_{i=0}^{k}(-1)^i \binom{n}{i} \binom{n}{k-i} x^k$ and the sum we want doesn't appear.

EDIT : indeed, I only have to look at the coefficient of $x^n$, which is $\binom{n}{i}\binom{n}{n-i} = \binom{n}{i}^2$.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Both boxed formulas in $(1)$ are correct. Note however, that the "correction" did not change anything since $\binom{2n-1}{n}=\binom{2n-1}{n-1}$; however, I prefer the form I had originally, since it is easier to see that $$n\binom{2n-1}{n}=(2n-1)\binom{2n-2}{n-1}$$. $\endgroup$ – robjohn Jan 11 '15 at 22:50
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ What question are you answering here? $\endgroup$ – Thomas Andrews Jan 8 '15 at 19:59
  • $\begingroup$ I'm giving an alternative approach to the sum he talks about at the beginning. $\endgroup$ – Jorge Fernández Hidalgo Jan 8 '15 at 20:00
  • $\begingroup$ I think he answer the first version... I've written $\binom{k}{n}$ instead of $\binom{n}{k}$ $\endgroup$ – Sebastien Jan 8 '15 at 20:00
  • $\begingroup$ So, in other words, you aren't answering the question. @ModdedBear $\endgroup$ – Thomas Andrews Jan 8 '15 at 20:01
  • 2
    $\begingroup$ But if you are writing a comment that is too long to be a comment, you should be clear upfront what you are talking about. Here, you just launch into an Answer which already answers something he knows how to answer, and you never say that in your post. It's always better, when posting a too-long-for-comment non-answer, to announce upfront what you are doing. Write, "An alternative approach to your first identity is..." $\endgroup$ – Thomas Andrews Jan 8 '15 at 20:04

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.