Combinatorial proof

**oldguynewstudent** · July 3rd 2010, 05:40 PM

Give a combinatorial proof: For n and k satisfying $1\leq k\leq n$ ,

$_{n}P_{k}=(n)_{k}=\sum_{j=k}^{n}k*(j-1)_{k-1}$ .

$\sum_{j=k}^{n}k*(j-1)_{k-1}$
$=k(k-1)_{k-1}+k(k)_{k-1}+k(k+1)_{k-1}+\ldots+k(n-2)_{k-1}+k(n-1)_{k-1}$

$=\frac{k*(k-1)!}{[(k-1)-(k-1)]!}+\frac{k*k!}{[k-(k-1)]!}+\frac{k(k+1)!}{[(k+1)-(k-1)]!}+\ldots+\frac{k(n-2)!}{[(n-2)-(k-2)]!}+\frac{k(n-1)!}{[(n-1)-(k-1)]!}<br />$
$=\frac{k(k-1)!}{0!}+\frac{k*k!}{1!}+\frac{k(k+1)!}{2!}+\ldots +\frac{k(n-2)!}{(n-k-1)!}+\frac{k(n-1)!}{(n-k)!}$ . When we factor out k(k-1)! we are left with

$1+k+\frac{k(k+1)}{2!}+\ldots+\frac{(n-k-1)!}{(n-k-1)!}+\frac{(n-k)!}{(n-k)!}=(n-k)??$

Now take (n-k)k(k-1)!=(n-k)k! and if we multiply by (n-k)!/(n-k)! we get (n-k)k!(n-k)!/(n-k)! = (n-k)n!/(n-k)!

This would equal $_{n}P_{k}=(n)_{k}=n!/(n-k)!$ except for the extra (n-k) in the numerator. Can someone please point out my mistake?

**kompik** · July 4th 2010, 12:16 AM

Originally Posted by oldguynewstudent

Give a combinatorial proof: For n and k satisfying $1\leq k\leq n$ ,

$_{n}P_{k}=(n)_{k}=\sum_{j=k}^{n}k*(j-1)_{k-1}$ .

If I understand the question correctly, (n)_k stands for Falling factorial.

I don't thinks the above forumla is true.
Try n=3, k=1.
Then the formula gives:
3=1.1+1.2+1.2!

Also, I think that would you tried is just manipulation sums, which is different form what I understand under combinatorial proof.

**oldguynewstudent** · July 4th 2010, 06:04 AM

Originally Posted by kompik

If I understand the question correctly, (n)_k stands for Falling factorial.

I don't thinks the above forumla is true.
Try n=3, k=1.
Then the formula gives:
3=1.1+1.2+1.2!

Also, I think that would you tried is just manipulation sums, which is different form what I understand under combinatorial proof.

For n=3, k=1 the formula gives $1*(0)_0 + 1*(1)_0 + 1*(2)_0 = 1+1+1=3$

I am new to combinatorial proofs, but this is the way I understand my professor did it in class. Just count things one way, then show that the other side comes out with the same counting result. I may be wrong but I will probably go see him before class on Tuesday. He is very good and the class is interesting but I think I did poorly on the test last Thursday. I only knew 7 out of 10 problems but my friends say he gives partial credit so I will have to see how it goes. Rotten luck! I knew how to do most of the problems he said would be on the test and none were extremely difficult. There were about 75 problems we had to study though. I really appreciate your help. Thank you very much.

**kompik** · July 4th 2010, 06:32 AM

Sorry for my mistake above :-(

Originally Posted by oldguynewstudent

Give a combinatorial proof: For n and k satisfying $1\leq k\leq n$ ,

$_{n}P_{k}=(n)_{k}=\sum_{j=k}^{n}k*(j-1)_{k-1}$ .

You could notice, that if you divide this by k!, you get
$\binom nk=\sum_{j=k}^{n} \binom{j-1}{k-1}$ ,
which is a well-known identity - identity (10) from Binomial coefficient - Wikipedia, the free encyclopedia ; proof can be found at Sum of k Choose m up to n - ProofWiki

**kompik** · July 4th 2010, 06:38 AM

Originally Posted by oldguynewstudent

When we factor out k(k-1)! we are left with

$1+k+\frac{k(k+1)}{2!}+\ldots+\frac{(n-k-1)!}{(n-k-1)!}+\frac{(n-k)!}{(n-k)!}=(n-k)??$

Now take (n-k)k(k-1)!=(n-k)k! and if we multiply by (n-k)!/(n-k)! we get (n-k)k!(n-k)!/(n-k)! = (n-k)n!/(n-k)!

I think you have a typo in the last two summands of this equation.
I do not understand, where do you get the RHS from.
You have n-k summands, only one of them is equal to one, so this cannot be equal to (n-k).

**oldguynewstudent** · July 4th 2010, 07:37 AM

Originally Posted by kompik

I think you have a typo in the last two summands of this equation.
I do not understand, where do you get the RHS from.
You have n-k summands, only one of them is equal to one, so this cannot be equal to (n-k).

$1+k+\frac{k(k+1)}{2!}+\ldots+\frac{(n-k-1)!}{(n-k-1)!}+\frac{(n-k)!}{(n-k)!}=(n-k)??$

You are correct in that the only way this adds to (n-k) is if k=1 which is an assumption that we cannot make. If k were 1, then we would have n-k terms equal to 1 which would be n-k.

**kompik** · July 4th 2010, 08:02 PM

Originally Posted by kompik

Sorry for my mistake above :-(

You could notice, that if you divide this by k!, you get
$\binom nk=\sum_{j=k}^{n} \binom{j-1}{k-1}$ ,
which is a well-known identity - identity (10) from Binomial coefficient - Wikipedia, the free encyclopedia ; proof can be found at Sum of k Choose m up to n - ProofWiki

You can find this as identity 135 in the book Benjamin, Quinn: Proofs that really count, together with a nice and easy combinatorial proof. Proofs that really count: the art of ... - Google Books

I found also this document http://www.cs.columbia.edu/~cs4205/files/CM4.pdf which seems to be a good resource for identities involving binomial coefficients and their proofs. This formula is Corollary 4.1.5 (but is written differently). (I posted a wrong link to proofwiki in the above post by mistake.)

Thread: Combinatorial proof

LinkBack

Thread Tools

Display

Combinatorial proof

Similar Math Help Forum Discussions

Combinatorial proof?

Combinatorial Proof

Combinatorial proof

Combinatorial proof help

Combinatorial Proof

Search Tags