• Support PF! Buy your school textbooks, materials and every day products Here!

Combinatorial Proofs of Binomial Identities

  • Thread starter silvermane
  • Start date
  • #1
silvermane
Gold Member
117
0

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.
 

Answers and Replies

  • #2
41
0
Try writing n^3 - n as (n+1)*n*(n-1).

Do you know something that this product counts?
 
  • #3
silvermane
Gold Member
117
0
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 :)
 
  • #4
41
0
Yeah, that should help.

Do you know how to interpret addition combinatorially? (If so, you probably have an idea of what to do next)
 
  • #5
silvermane
Gold Member
117
0
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) =/
 
  • #6
41
0
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.
 
  • #7
silvermane
Gold Member
117
0
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! =)
 
  • #8
silvermane
Gold Member
117
0
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?
 
  • #9
41
0
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?
 
  • #10
silvermane
Gold Member
117
0
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 :)
 

Related Threads for: Combinatorial Proofs of Binomial Identities

Replies
1
Views
3K
Replies
0
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
0
Views
861
  • Last Post
Replies
6
Views
944
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
3K
Top