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.


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


and the one for odd $n$ can be written


For $(1)$ note that


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


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.)

| cite | improve this answer | |

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.

| cite | improve this answer | |

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

| cite | improve this answer | |

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.