Combinatorial Proofs of Binomial Identities

[silvermane]

Homework Statement

(Give a combinatorial proof of each of the following identities. In other words, describe a collection of combinatorial objects and then explain two different methods for counting those objects. Leave each identity in the form given. Do not rearrange terms or use any other identity to simplify the equation.)

Prove that for n greater than or equal to 3,
n^3 - n = 6(nC3) + 6(nC2)

The Attempt at a Solution

This is my first Combinatorics class, and I must say that I don't think like this at all. It's all new to me and I don't understand anything in a combinatorial sense, but rather I understand things inductively and algebraically. Please give me a hint in how I could do this. I don't exactly want an answer, just a little help. Thank you so much for your time.

 

[Mathnerdmo]

Try writing n^3 - n as (n+1)*n*(n-1).

Do you know something that this product counts?

 

[silvermane]

Try writing n^3 - n as (n+1)*n*(n-1).

Do you know something that this product counts?

Yeah, say we have a group of n+1 people and we want to have 3 of them sit down in 3 chairs. We could seat the first person in N+1 ways.
The second person in N ways.
The third in N - 1 ways.
(I write it as this because this is how the prof wants it in our hmwk)


I think I understand how to count the left side of the equation. The right side is kinda throwing me off a little here, but I think I simplified it correctly.

Say we arrange the right side as 3x2x(nC3)+3x2x(nC2) and look at it this way for the proof.
Lemme know if I'm on the right track. You've been very helpful :)

 

[Mathnerdmo]

Yeah, that should help.

Do you know how to interpret addition combinatorially? (If so, you probably have an idea of what to do next)

 

[silvermane]

Yeah, that should help.

Do you know how to interpret addition combinatorially? (If so, you probably have an idea of what to do next)

Uh, that's where I am stuck. We just learned summation notation, and he just gave us this. We know that you can take separate cases and add them, but I don't know how to put it into my example. (sorry for being a burden) =/

 

[Mathnerdmo]

We know that you can take separate cases and add them

Actually, that's all I meant. If you're adding two numbers together, you're just considering two separate cases.

Think about why (n+1) isn't explicitly appearing on the right-hand side. It'll help you figure out what two cases will work.

 

[silvermane]

Actually, that's all I meant. If you're adding two numbers together, you're just considering two separate cases.

Think about why (n+1) isn't explicitly appearing on the right-hand side. It'll help you figure out what two cases will work.

Okay, that helps out a lot. Thank you! =)

 

[silvermane]

I Understand it in terms of Pascal's triangle and used an example with giving people medals. The only problem is that when I discussed the problem with the professor, I found that we are not allowed to alter the equation in any way.

I have to explain it as a difference rule on the left side, n^3 - n
and it must be 6(nC3) + 6(nC2) for the right side.

I know how to explain the right side, but I am having some trouble with the left side and using the difference rule. I know that n^3 is the number of ways to distribute the medals to the people before the race, where the case of one person getting all three medals is included. I don't know why I would subtract by n though. Any ideas?

 

[Mathnerdmo]

I Understand it in terms of Pascal's triangle and used an example with giving people medals. The only problem is that when I discussed the problem with the professor, I found that we are not allowed to alter the equation in any way.

I have to explain it as a difference rule on the left side, n^3 - n
and it must be 6(nC3) + 6(nC2) for the right side.

I know how to explain the right side, but I am having some trouble with the left side and using the difference rule. I know that n^3 is the number of ways to distribute the medals to the people before the race, where the case of one person getting all three medals is included. I don't know why I would subtract by n though. Any ideas?

All right. I don't think you'd be able to use pascal's triangle, but I don't think my instructors had a problem with factoring...

What if we don't allow the case of one person getting all three medals? How many ways have we removed when we disallow this?

 

[silvermane]

All right. I don't think you'd be able to use pascal's triangle, but I don't think my instructors had a problem with factoring...

What if we don't allow the case of one person getting all three medals? How many ways have we removed when we disallow this?

Yeah, I did just what you said before reading this! It turns out that it works that way just fine. Thanks for your help :)