Math Is Fun Forum

simron

Real Member

Registered: 2006-10-07

Posts: 237

Prove, using comittee-forming...

... that C(n, 0)[sup]2[/sup] + C(n, 1)[sup]2[/sup] +...+ C(n, n-1)[sup]2[/sup] + C(n, n)[sup]2[/sup]= C(2n, n) (thanks bobbym for reminding me what this added to). This is for a class, Introduction To Counting And Geometry, and this problem set is due tomorrow, so any help would be appreciated.

Last edited by simron (2009-05-25 10:34:17)

---

Linux FTW

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Prove, using comittee-forming...

Hi simron;
If you are try to sum the squares of binomials then I remember that sum is equal to

The proof is difficult and I am sorry that I can not provide an easier one.

The series can be rewritten like this.

We prove this with a combinatorial argument. If we want to select n things out of 2n things we could separate the things into 2 piles each with n things in them.

There are

ways to select k things from the first pile and

ways to take n-k objects from the second pile to make up a selection of n things. So the number of ways to make the selection is

This is out of an Introduction to Combinatorics by C.L. Liu a horrible book. It is the only proof I know that uses a combinatorial argument. There is another proof that uses generating functions but it is even tougher.

Last edited by bobbym (2009-05-24 21:26:12)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Kurre

Member

Registered: 2006-07-18

Posts: 280

Re: Prove, using comittee-forming...

Write it as C(n,0)*C(n,n)+C(n,1)*C(n,n-1)+...+C(n,k)*C(n,n-k)+...+C(n,n)*C(n,0).
Then assume you have a set of 2n persons, and divide it into two sets A and B of n persons in each. Now you want to choose a comittee of n persons. Then for each choice there will be say k persons in set A, and n-k persons in set B, and summing will yield exactly the sum above.

simron

Real Member

Registered: 2006-10-07

Posts: 237

Re: Prove, using comittee-forming...

Hey, thanks!
I also need to prove it using block-walking. Any ideas?

---

Linux FTW

Kurre

Member

Registered: 2006-07-18

Posts: 280

Re: Prove, using comittee-forming...

what do you mean by block walking?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Prove, using comittee-forming...

Hi Kurre;

  Block walking is the actual walking of paths on a 2D lattice. It is similar to walking in a city with a rectangular grid of streets. Many sums and recurrences that occur in combinatorics can be evaluated and proved using it.

Last edited by bobbym (2009-05-24 21:09:09)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Prove, using comittee-forming...

Hi simron;

  I don't remember how to prove that sum using a block walking argument. I have searched the net and can find no demonstration of it. Looking through my own library now, if I find it I will post it.

Nearest thing is:
http://server251.theory.cs.cmu.edu/twiki/bin/view/Main/CountingThree
goto summing and squaring in pascals triangle.

This is related to block walking because the numbers in pascals triangle correspond to the number of ways to reach each lattice point of a 2X2 grid. His demonstration is not a proof though. just evidence to suggest your sum.

Last edited by bobbym (2009-05-24 23:12:25)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.