Combinatorial Proof

**oldguynewstudent** · June 2nd 2010, 08:51 PM

Attached is the section on Combinatorial Proofs from my text. I am a little confused. I understand the proof of the special case, then it goes on to say "It is no harder to prove in general."

I would prove this identity in the following manner but I'm not sure if the following is a combinatorial proof or not. Please let me know if it is, or if it is not a combinatorial proof, please point me to a resource so I will understand it better.

Prove the identity: $(n)_{k}=(n-1)_{k}+k*(n-1)_{k-1}$

LHS $(n)_{k}=\frac{n!}{(n-k)!}$

RHS $(n-1)_{k}+k*(n-1)_{k-1}=\frac{(n-1)!}{(n-1-k)!}+\frac{k*(n-1)!}{(n-1-k+1)!}=$
$\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)!}=\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)(n-k-1)!}=$
$\frac{(n-k)(n-1)!+k*(n-1)!}{(n-k)(n-k-1)!}=\frac{(n-k+k)(n-1)!}{(n-k)!}=\frac{n(n-1)!}{(n-k)!}=\frac{n!}{(n-k)!}$

Since the LHS equals the RHS this completes the proof.

Please let me know if the above is a combinatorial proof or not.

**undefined** · June 2nd 2010, 09:12 PM

Originally Posted by oldguynewstudent

Attached is the section on Combinatorial Proofs from my text. I am a little confused. I understand the proof of the special case, then it goes on to say "It is no harder to prove in general."

I would prove this identity in the following manner but I'm not sure if the following is a combinatorial proof or not. Please let me know if it is, or if it is not a combinatorial proof, please point me to a resource so I will understand it better.

Prove the identity: $(n)_{k}=(n-1)_{k}+k*(n-1)_{k-1}$

LHS $(n)_{k}=\frac{n!}{(n-k)!}$

RHS $(n-1)_{k}+k*(n-1)_{k-1}=\frac{(n-1)!}{(n-1-k)!}+\frac{k*(n-1)!}{(n-1-k+1)!}=$
$\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)!}=\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)(n-k-1)!}=$
$\frac{(n-k)(n-1)!+k*(n-1)!}{(n-k)(n-k-1)!}=\frac{(n-k+k)(n-1)!}{(n-k)!}=\frac{n(n-1)!}{(n-k)!}=\frac{n!}{(n-k)!}$

Since the LHS equals the RHS this completes the proof.

Please let me know if the above is a combinatorial proof or not.

I'm used to seeing $(n)_k$ as $P(n,k)$ but now that I see what we're talking about..

The author writes that "It is no harder to prove in general" because you can follow the exact same methodology as the concrete proof for the general proof, only replacing 6 with n, 5 with n-1, 4 with k, and 3 with k-1. The only potentially sticky point is when n=1 or k=1.

So, no need to write out all the long expressions you wrote. Just basically copy out the book proof with variables in place of numbers.

**Archie Meade** · June 3rd 2010, 04:53 AM

Originally Posted by oldguynewstudent

Attached is the section on Combinatorial Proofs from my text. I am a little confused. I understand the proof of the special case, then it goes on to say "It is no harder to prove in general."

I would prove this identity in the following manner but I'm not sure if the following is a combinatorial proof or not. Please let me know if it is, or if it is not a combinatorial proof, please point me to a resource so I will understand it better.

Prove the identity: $(n)_{k}=(n-1)_{k}+k*(n-1)_{k-1}$

LHS $(n)_{k}=\frac{n!}{(n-k)!}$

RHS $(n-1)_{k}+k*(n-1)_{k-1}=\frac{(n-1)!}{(n-1-k)!}+\frac{k*(n-1)!}{(n-1-k+1)!}=$
$\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)!}=\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)(n-k-1)!}=$
$\frac{(n-k)(n-1)!+k*(n-1)!}{(n-k)(n-k-1)!}=\frac{(n-k+k)(n-1)!}{(n-k)!}=\frac{n(n-1)!}{(n-k)!}=\frac{n!}{(n-k)!}$

Since the LHS equals the RHS this completes the proof.

Please let me know if the above is a combinatorial proof or not.

Yes, this correctly proves that $Np_K=[N-1]p_K+K[N-1]p_{K-1}$

**awkward** · June 3rd 2010, 04:36 PM

Hi oldguynewstudent,

Your proof is correct, but it is not what is called a "combinatorial proof". See

Combinatorial proof - Wikipedia, the free encyclopedia

Some mathematicians feel that combinatorial proofs are better than other types of proof because they give more insight into the problems. I'm not sure everyone agrees with this.

In order to have a combinatorial proof, you need to show that the two sides of your equation are essentially two different ways of counting the same set of objects. There may well be more than one way of doing this, but for example, $(n)_k$ is the number of permutations of n objects taken k at a time. If you can show that the RHS also counts the same set of permutations, that will constitute a combinatorial proof.

[Edit] Your book uses the number of ways to distribute k objects among n people in its sketch of the proof, which is another approach to the same identity. (I was a little slow to read the thumbnails.) But the idea of what it takes for a "combinatorial proof" is the same.[/edit]

**Archie Meade** · June 4th 2010, 02:24 PM

$^{n-1} P_{k}$ is the number of ways to arrange k distinct elements from n-1 distinct elements.

If we arrange k from a group of elements with one more element,
then we will have all arrangements already counted by the $^{n-1}P_k$ formula,

while extra arrangements will include the added element arranged with all
original n-1 elements but taking k-1 of them at a time as the added element
forms a group of k elements with them.

This means that we will be arranging k-1 of the n-1 elements together with the
added element, which can fit into any of the k positions, giving us k times
the arrangements of k-1 from n-1.

By this logic..

$^{n-1}P_k+k\left(^{n-1}P_{k-1}\right)$ must equal $^nP_k$

Your proof then shows that this is the case.

**awkward** · June 4th 2010, 04:12 PM

Correct, that is a "combinatorial proof".

Thread: Combinatorial Proof

LinkBack

Thread Tools

Display

Combinatorial Proof

Similar Math Help Forum Discussions

Combinatorial Proof

Combinatorial proof

Combinatorial proof help

combinatorial proof

Combinatorial proof

Search Tags