-2
$\begingroup$

I don't know if this question is trivial but let me put it in the first place. I'm trying to find the sum of $\binom{n}{0}^2+\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n-1}^2+\binom{n}{n}^2$ or equivalently $\displaystyle \sum_{k=0}^n \binom{n}{k}^2$.

How would you proceed?

$\endgroup$

marked as duplicate by Holo, Hans Lundmark, user90369, Cesareo, Carl Schildkraut Oct 10 '18 at 23:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What have you tried? $\endgroup$ – Jaroslaw Matlak Oct 10 '18 at 14:57
  • $\begingroup$ You should not say that without providing a link, because I am pretty involved in mathematics and I did not know that. $\endgroup$ – HackerBoss Oct 10 '18 at 15:00
  • $\begingroup$ Agreed. It is equal to $\binom{2n}n$, which can be proved using a combinatorial argument. $\endgroup$ – астон вілла олоф мэллбэрг Oct 10 '18 at 15:01
  • $\begingroup$ It is $$\frac{2^{2 n} \Gamma \left(n+\frac{1}{2}\right)}{\sqrt{\pi } \Gamma (n+1)}$$ $\endgroup$ – Dr. Sonnhard Graubner Oct 10 '18 at 15:02
  • $\begingroup$ It is a special case of Vandermonde's identity $\endgroup$ – Sil Oct 10 '18 at 15:03
1
$\begingroup$

lets first prove a more general thing, i.e,

$\sum_{i = 0}^{x} {n \choose i } {m \choose x - i } = {m + n \choose x}$.

For that, let's suppose we have m apples and n oranges, and now we want to choose x fruits from them, we can do it in ${m + n \choose x}$ ways, and that's RHS. Now we can also select x fruits, by selecting 0 apples and x oranges, 1 apple and x - 1 oranges and so on, and that's exactly LHS, and hence LHS = RHS.

Now just put m = n, and x = n, in the equation, so it becomes

$\sum_{i = 0}^{n} {n \choose i}{n \choose n - i} = {2n \choose n}$

or,

$\sum_{i = 0}^{n} {n \choose i} {n \choose i} = {2n \choose n}$

$\sum_{i = 0}^{n} {n \choose i}^2 = {2n \choose n}$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.