Problem related to series of binomial coefficients

Question

Problem related to series of binomial coefficients in which each term is a product of two binomial coefficients.

In this question:

Prove that $$\binom{n}0^2+\binom{n}1^2+\ldots+\binom{n}n^2=\frac{(2n)!}{n!n!}$$

What I did was equate the coefficient of $x^n$ in

$$\begin{align*} &\left(\binom{n}0+\binom{n}1x+\binom{n}2x^2+\ldots+\binom{n}nx^n\right)\left(\binom{n}0x^n+\binom{n}1x^{n-1}+\ldots+\binom{n}n\right)\\ &=(1+x)^{2n} \end{align*}$$

I came across a similar question:

Prove that $$\binom{n}0^2-\binom{n}1^2+\ldots+(-1)^n\binom{n}n^2$$ is $0$ or $\dfrac{(-1)^{n/2}n!}{(n/2)!(n/2)!}$ according as $n$ is odd or even.

I did the same thing by taking $(1-x)^n$ and $(x-1)^n$ but I'm not getting the answer.

Please help.

Answer 1

Split it into two identities. The one for even $n$ can be written

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

and the one for odd $n$ can be written

$$\sum_{k=0}^{2n+1}(-1)^k\binom{2n+1}k^2=0\;.\tag{2}$$

For $(1)$ note that

$$\left(\sum_{k=0}^{2n}(-1)^k\binom{2n}kx^k\right)\left(\sum_{k=0}^{2n}\binom{2n}kx^k\right)=(1-x)^{2n}(1+x)^{2n}=(1-x^2)^{2n}\;.\tag{3}$$

The coefficient of $x^{2n}$ in $(1-x^2)^{2n}$ is $(-1)^n\binom{2n}n$. On the other hand, the coefficient of $x^{2n}$ in the product on the lefthand side of $(3)$ is

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

this establishes $(1)$.

Now see if you can adapt the same idea to handle $(2)$. (You can actually handle both at once, but it may be a little simpler to consider them separately.)

Answer 2

Here is a combinatorial proof. Take a set of $2n$ elements and count how many ways we can partition it into two sets, each with $n$ elements. The order of the two sets matters. Let's all this count $C$.

One way to count the partitions is to choose $n$ elements out of the $2n$ elements for the first set, and the remaining elements go in the second set. This makes, of course,

$$C={2n \choose n}=\frac{(2n)!}{n!n!}$$

Now let's subdivide those partitions in the number of elements in the first set. Let's say the first set in the partition has $k$ elements from $1,2,\ldots,n$, and that means it has $n-k$ elements from $n+1,n+2,\ldots,2n$. So for a given $k$ we can choose that first set of $k$ elements in this many ways:

$$C_k={n \choose k}\cdot{n \choose n-k}={n \choose k}\cdot{n \choose k}={n \choose k}^2$$

That middle equality is by the symmetry of the binomial coeffients. Adding up the $C_k$,

$$C=\sum_{k=0}^n C_k$$ or $$\frac{(2n)!}{n!n!}=\sum_{k=0}^n {n \choose k}^2$$

which is what you wanted.

Answer 3

Vandermonde's identity says

$${(m+n)\choose r} = \sum_{k=0}^{r} {m\choose k}{n\choose (r-k)}$$

Put $m = n$, $n = n$, and $r = n$.

You get$$ {(2n)\choose n} = {n\choose 0}{n\choose n}+{n\choose 1}{n\choose (n-1)}+\cdots + {n\choose n}{n\choose n}$$

$${(2n)\choose n} = {(n)\choose 0}^2+{(n)\choose 1}^2+\cdots+{(n)\choose n}^2\tag1$$