Waste less time on Facebook — follow Brilliant.

Proving a combinatorial identity

Prove that

\[ {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \dots + {n \choose n}^2 = {2n \choose n}. \]

Like with most such problems, there are probably many ways to prove this. I proved this by showing that the LHS is an alternative way of choosing \(n\) objects from a group of \(2n\) distinct objects. Divide this group in two groups \(A,B\) each with size \(n\). You can choose any number of objects from group \(A\), call this number \(k\). This can be done in \(n \choose k\) ways. Obviously, \(0 \leq k \leq n\). Because you pick \(n\) objects in total, you still have to choose \(n-k\) objects from group \(B\), which can be done in \({n \choose {n-k}}\) ways. But we know that for every \(0 \leq k \leq n\) with nonnegative \(n,k\), that

\[{n \choose {n-k}} = {n \choose k},\]

so choosing \(n-k\) objects from group \(B\) can also be done in \(n \choose k\) ways. Therefore,

\[ \sum\limits_{k=0}^n {n \choose k}^2 = {2n \choose n},\]

which is what we wanted.

Like I said, there are probably other ways to prove this identity, e.g. by using the binomial theorem. Does anyone have an idea?

Note by Tim Vermeulen
4 years ago

No vote yet
4 votes


Sort by:

Top Newest

I have a method, \(\normalsize(1+x)^{n}(1+\frac{1}{x})^{n} = [{n \choose 0}+{n \choose 1}x +{n \choose 3}x^{2}....+{n \choose n}x^{n}] \times [{n \choose 0}+{n \choose 1}\frac{1}{x} + {n \choose 2}\frac{1}{x^{2}}....+{n \choose n}\frac{1}{x^{n}}]\) So,terms on R.H.S which are independent of \(x\) are \(\normalsize{n \choose 0}^{2} + {n \choose 1}^{2} +...........+ {n \choose n}^{2}.\) L.H.S= \(\normalsize\frac{(1+x)^{2n}}{x^{n}}\) So term independent of \(x\) on L.H.S = \(\normalsize{2n \choose n}.\) Hence proved.Please correct me If I am wrong....! Kishan K · 4 years ago

Log in to reply

@Kishan K How do you mean "L.H.S= \(\normalsize\frac{(1+x)^{2n}}{x^{n}}\)"? Tim Vermeulen · 4 years ago

Log in to reply

@Tim Vermeulen \(\large(1+x)^{n}(1+\frac{1}{x})^{n}= (1+x)^{n}(\frac{1+x}{x})^{n}= (1+x)^{n}\frac{(1+x)^{n}}{x^{n}}=\frac{(1+x)^{2n}}{x^{n}}.\) Now for being independent of \(x\) in L.H.S, the power of \(x\) in the expansion of numerator must be \(n\), so to be canceled out by the denominator one.So coefficient of \(\large x^{n}= {2n \choose n}\).Please correct me.. Kishan K · 4 years ago

Log in to reply

@Kishan K That's really cool. I've seen many combinatorial proofs in which they prove that the coefficients of say \(x\) are equal, or \(x^n\), but never that the coefficients of \(x^0\) are equal, i.e. the constant term. Well done! Tim Vermeulen · 4 years ago

Log in to reply

This is just a special case of the Vandermonde identity with m=r=n. Some proofs can be found on that wikipedia page. You can also prove Vandermonde simply by induction on m. Yonatan Naamad · 4 years ago

Log in to reply

Another approach would be to compare the coefficients of \( (x+1)^{2n} \) and \( (x+1)^n(x+1)^n \). The coefficient of \(x^a\) (\( 1 \leq a \leq n \)) in the \(L.H.S\) is \( {2n \choose a} \), and that in the \(R.H.S\) is the sum of all possible values of \( {n \choose i}{n \choose j} \), where \( i \) and \(j\) are non-negative integers which sum to \(a\) (this is because in \( (x+1)^n(x+1)^n \), we can take any degree of \(x\) from the first bracket, which is \(i\), and the other degree of \(x\) from the second bracket, which is \(j\), and for their product to be equal to \(a\), we must have \(i+j= a\) ). Comparing coefficients and setting \(a= n\), the result follows.

Edit:- After revising my proof, I found out that it is somewhat analogous to that submitted by Tim V. In the proof in the discussions body, a group of \(2n\) objects is divided into \(2\) groups of \(n\) objects, and \(i\) objects are chosen from the first group, \(n-i\) from the other. Basically in my proof, a collection of \(2n\) \(x\)s (\((x+1)^{2n}\)) is divided into two groups consisting of \(x\)s (the two brackets in the \(R.H.S\)). From the first bracket, \(i\) elements are chosen, and \(n-i\) are chosen from the second one. So I don't think my proof is different from that already posted. :( Sreejato Bhattacharya · 4 years ago

Log in to reply

@Sreejato Bhattacharya Hi, It's called "convolution of generating functions", it can be used to derive many more such identities! Gopinath No · 4 years ago

Log in to reply

@Sreejato Bhattacharya That's not a problem, it's just another way of explaining it :) Tim Vermeulen · 4 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...