0
$\begingroup$

Within another answer to a question concerning a sums of the type

$$\sum_{k=0}^n \binom{n}{k}^2$$

there was a simple indetity given which reduces this sum to a simple binomial coefficient, to be exact to

$$\binom{2n}{n}$$

However I tried to prove the formula

$$\sum_{k=0}^n \binom{n}{k}^2~=~\binom{2n}{n}$$

by induction and failed. Overall my attempt was to split up the sum for $n=m+1$ as follows

$$\sum_{k=0}^{m+1} \binom{m+1}{k}^2~=~\sum_{k=0}^m \binom{m+1}{k}^2 + \binom{m+1}{m+1}^2~=~(m+1)^2\sum_{k=0}^m \frac1{(m+1-k)^2}\binom{m}{k}^2 +1$$

I now stuck at reshaping this sum in the end and to substitute it by

$$\binom{2m}{m}$$

so I guess either induction is not the right way to approach to this proof or I made a critical error somewhere. I would be interested in a right proof and a explanation why my attempt did not worked out.

Thank you in advance.


I just figured out this formula is called Vandermondes Identity and it can be derived in way from the Binomial Theorem. But I am still interested in a proof maybe without this property.

$\endgroup$
  • 2
    $\begingroup$ It is a particular case of Vandermonde's identity (aka the Chu--Vandermonde identity), which states that $\dbinom{x+y}{n} = \sum\limits_{k=0}^n \dbinom{x}{k}\dbinom{y}{n-k}$ for any nonnegative integer $n$ and any reasonable $x$ and $y$ (these can be commuting indeterminates, or just real numbers). For two proofs that don't use the binomial theorem, see the proofs of Theorem 2.27 in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, version of 26 April 2018. $\endgroup$ – darij grinberg Jul 24 '18 at 13:11
3
$\begingroup$

EDIT: After posting, I saw the edit to the question asking for a proof without using the binomial theorem. Unfortunately, I don't have one, but I'll leave this answer posted since it is a correct proof.

Look at the coefficient of $x^n$ in the expansion of $(1+x)^{2n}.$ By the binomial theorem, we have $$(1+x)^{2n} = \sum^{2n}_{k=0} \binom{2n}{k} x^k$$ and thus the coefficient of $x^n$ is $\binom{2n}n$. On the other hand, we have $$(1+x)^{2n} = \big((1+x)^n\big)^2 = \left(\sum^n_{\ell=0} \binom{n}\ell x^\ell \right)^2.$$ When we square this sum, the terms that produce $x^n$ are those of the form $x^\ell\cdot x^{n-\ell}$ and the corresponding coefficient is $\binom n \ell \binom{n}{n-\ell}$. But $\binom n \ell = \binom{n}{n-\ell}$, so these coefficients are $\binom{n}\ell^2$. Since one of these occur for each $\ell=0,\ldots,n$, we see that the whole coefficient of $x^n$ is $\sum^n_{\ell=0} \binom{n}{\ell}^2$ and thus $$\binom{2n}n = \sum^n_{\ell=0} \binom n \ell^2.$$

$\endgroup$
  • $\begingroup$ Ah, thank you. That is a quite elegant way to prove this. $\endgroup$ – mrtaurho Jul 23 '18 at 13:24
2
$\begingroup$

Maybe it is interesting to see that using the integral representation of the binomial coefficient $$\dbinom{n}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=\epsilon}\frac{\left(1+z\right)^{n}}{z^{k+1}}dz$$ we get $$\sum_{k=0}^{n}\dbinom{n}{k}^{2}=\frac{1}{2\pi i}\oint_{\left|z\right|=\epsilon}\frac{\left(1+z\right)^{n}}{z}\sum_{k=0}^{n}\dbinom{n}{k}z^{-k}dz$$ $$=\frac{1}{2\pi i}\oint_{\left|z\right|=\epsilon}\frac{\left(1+z\right)^{n}}{z}\left(1+\frac{1}{z}\right)^{n}dz=\frac{1}{2\pi i}\oint_{\left|z\right|=\epsilon}\frac{\left(1+z\right)^{2n}}{z^{n+1}}dz=\dbinom{2n}{n}.$$

$\endgroup$
0
$\begingroup$

Suppose you have a set of size $2n$. Divide it into two subsets of size $n$. You know that $2n\choose n$ is the number of subsets of size $n$ from the $2n$ elements.

Let $k$ be an integer $0 \le k \le n$. Let $E_k$ be the set of all subsets of size $n$ where $k$ are chosen from one of the two subsets of size $n$ and $n-k$ from the other. Then $E_k$ has $${n\choose n-k}{n\choose k} = {n\choose k}^2$$ elements. I think you can see the rest.

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