Proving a combinatorial identity

Prove that

(n0)2+(n1)2+(n2)2++(nn)2=(2nn). {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 nn objects from a group of 2n2n distinct objects. Divide this group in two groups A,BA,B each with size nn. You can choose any number of objects from group AA, call this number kk. This can be done in (nk)n \choose k ways. Obviously, 0kn0 \leq k \leq n. Because you pick nn objects in total, you still have to choose nkn-k objects from group BB, which can be done in (nnk){n \choose {n-k}} ways. But we know that for every 0kn0 \leq k \leq n with nonnegative n,kn,k, that

(nnk)=(nk),{n \choose {n-k}} = {n \choose k},

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

k=0n(nk)2=(2nn), \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
6 years, 2 months ago

No vote yet
4 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

I have a method, (1+x)n(1+1x)n=[(n0)+(n1)x+(n3)x2....+(nn)xn]×[(n0)+(n1)1x+(n2)1x2....+(nn)1xn]\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 xx are (n0)2+(n1)2+...........+(nn)2.\normalsize{n \choose 0}^{2} + {n \choose 1}^{2} +...........+ {n \choose n}^{2}. L.H.S= (1+x)2nxn\normalsize\frac{(1+x)^{2n}}{x^{n}} So term independent of xx on L.H.S = (2nn).\normalsize{2n \choose n}. Hence proved.Please correct me If I am wrong....!

Kishan k - 6 years, 2 months ago

Log in to reply

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

Tim Vermeulen - 6 years, 2 months ago

Log in to reply

(1+x)n(1+1x)n=(1+x)n(1+xx)n=(1+x)n(1+x)nxn=(1+x)2nxn.\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 xx in L.H.S, the power of xx in the expansion of numerator must be nn, so to be canceled out by the denominator one.So coefficient of xn=(2nn)\large x^{n}= {2n \choose n}.Please correct me..

Kishan k - 6 years, 2 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 xx are equal, or xnx^n, but never that the coefficients of x0x^0 are equal, i.e. the constant term. Well done!

Tim Vermeulen - 6 years, 2 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 - 6 years, 2 months ago

Log in to reply

Another approach would be to compare the coefficients of (x+1)2n (x+1)^{2n} and (x+1)n(x+1)n (x+1)^n(x+1)^n . The coefficient of xax^a (1an 1 \leq a \leq n ) in the L.H.SL.H.S is (2na) {2n \choose a} , and that in the R.H.SR.H.S is the sum of all possible values of (ni)(nj) {n \choose i}{n \choose j} , where i i and jj are non-negative integers which sum to aa (this is because in (x+1)n(x+1)n (x+1)^n(x+1)^n , we can take any degree of xx from the first bracket, which is ii, and the other degree of xx from the second bracket, which is jj, and for their product to be equal to aa, we must have i+j=ai+j= a ). Comparing coefficients and setting a=na= 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 2n2n objects is divided into 22 groups of nn objects, and ii objects are chosen from the first group, nin-i from the other. Basically in my proof, a collection of 2n2n xxs ((x+1)2n(x+1)^{2n}) is divided into two groups consisting of xxs (the two brackets in the R.H.SR.H.S). From the first bracket, ii elements are chosen, and nin-i are chosen from the second one. So I don't think my proof is different from that already posted. :(

Sreejato Bhattacharya - 6 years, 2 months ago

Log in to reply

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

Tim Vermeulen - 6 years, 2 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 - 6 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...