Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-05-24 09:06:26

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. tongue

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


Linux FTW

Offline

#2 2009-05-24 10:29:34

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.

Offline

#3 2009-05-24 11:13:48

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.

Offline

#4 2009-05-24 11:20:01

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

Offline

#5 2009-05-24 18:33:52

Kurre
Member
Registered: 2006-07-18
Posts: 280

Re: Prove, using comittee-forming...

what do you mean by block walking? yikes

Offline

#6 2009-05-24 21:07:22

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.

Offline

#7 2009-05-24 21:11:44

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.

Offline

Board footer

Powered by FluxBB