# Prove $\sum_{i=0}^{n} \binom{n}{i}^2 = \binom{2n}{n}$ [duplicate]

This is a workshop task i've been given for my combinatorics module, the only hint i've been given towards it is: 'Suppose we have n blue balls and n red balls. What do both quantities above describe?'

I started thinking about the problem by noting that the right hand side is the number of subsets of $$2n$$ of size $$n$$. And also $$\binom{n}{i}$$ is the number of subsets of n of size $$i$$. so let $$i=0$$ and we have $$1$$ way to make a subset of size zero, then $$\binom{n}{1} = n$$ and so on. Thinking about it with the 'hint' i can describe the LHS as being the number of different ways we can take $$i$$ balls out of the bag and when all combinations are added together, it becomes the total number of ways we can take any number of balls ($$i \leq n$$) from the bag.

The RHS is the number of subsets of $$2n$$ of size $$n$$, or the number of ways we can take $$n$$ balls out of a bag of size $$n$$, using the hint, if we have a bag of $$n$$ blue and $$n$$ red balls it's the total number of ways we can pull out $$n$$ number of balls where so many are red and blue, e.g $$1$$ red and $$(n-1)$$ blue.

I can see all this but I have no clue how either side even relates let alone is equal.

$$(1+x)^n(1+x)^n=(1+x)^{2n}.$$

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

$$(1+x)^n(1+x)^n=\sum_{i=0}^n\sum_{j=0}^n\binom{n}{i}\binom{n}{j}x^{i+j}.$$ Therefore, $$\binom{2n}{n}=\sum_{i=0}^n\sum_{i+j=n}\binom{n}{i}\binom{n}{j}=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}=\sum_{i=0}^n\binom{n}{i}^2.$$

• You see i was thinking about that but i thought it was flat out incorrect to say that, i know $\sum_{i=0}^{n} \binom{n}{i} = 2^n$ but didn't think i could just write $\sum_{i=0}^{n} \binom{n}{i}^2 = 2^{n}2^{n}$. I think that's what you're hinting at anyway – L G May 3 '19 at 12:34
• @LG: Could you tell me the link between $\sum_{i=0}^n\binom{n}{i}$ and $\sum_{i=0}^n\binom{n}{i}^2$ ? Anyway, I updated my answer. – Surb May 3 '19 at 12:38
• I believed that there is no direct relation. But I'm probably incorrect, I'm trying to find it out but your updated answer makes a lot of sense, where $i$ is the 'selected' number of balls and $j$ the 'rejected'. – L G May 3 '19 at 12:42