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, 3 months ago

No vote yet
4 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

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, 3 months ago

Log in to reply

How do you mean "L.H.S= \(\normalsize\frac{(1+x)^{2n}}{x^{n}}\)"?

Tim Vermeulen - 4 years, 3 months ago

Log in to reply

\(\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, 3 months 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, 3 months 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, 3 months 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, 3 months ago

Log in to reply

Hi, It's called "convolution of generating functions", it can be used to derive many more such identities!

Gopinath No - 4 years, 3 months ago

Log in to reply

That's not a problem, it's just another way of explaining it :)

Tim Vermeulen - 4 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...