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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**simron****Real Member**- Registered: 2006-10-07
- Posts: 237

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

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

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 isThis 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

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

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

**simron****Real Member**- Registered: 2006-10-07
- Posts: 237

Hey, thanks!

I also need to prove it using block-walking. Any ideas?

Linux FTW

Offline

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

what do you mean by block walking?

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

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

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

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

Pages: **1**