# Combinatorial Proofs for $n^3-n= 6\binom{n}{2}+ 6\binom{n}{3}$

I am learning about combinatorial proofs and I found it very interesting. One proof can be elegantly done while algebraic proofs can be tedious. However, I had a hard time come up with a combinatorial proof for the following equality. (My thought is that $$n^3-n$$ is really $$P(n+1,3)$$ and I can kind of see how 6 is coming (since $$6 = 3!$$) but then I don't know where to go next)

$$n^3-n= 6C(n,2) + 6C(n,3)$$

and I'd appreciate if you can shed some light so that I can keep going. Thanks ahead!

• Yes, thanks for reminding.
– user48601
Commented Dec 19, 2013 at 1:06
• Just a note, this is an example where things are the other way round, the algebraic proof is trivial. Commented Dec 19, 2013 at 1:09
• Right, I agree, but what would be a combinatorial proof for this one? I usually use "forming a committee" to approach problems like this but I don't know.
– user48601
Commented Dec 19, 2013 at 1:13

Divide through by $6$, and you can rewrite it as $$\binom{n+1}3=\binom{n}2+\binom{n}3\;,$$ which is just a special case of the Pascal’s triangle identity, which in turn has a straightforward combinatorial proof.

• Oh, it's you again, thanks for the answer!
– user48601
Commented Dec 19, 2013 at 1:19
• Let's me think if I can use some thing like the combinatorial proof in the pascal's. I did the pascal's two days ago..
– user48601
Commented Dec 19, 2013 at 1:20
• @Victoria: You’re welcome! Feel free to leave a comment if you get stuck. Commented Dec 19, 2013 at 1:21
• Okay: here comes the proof. I am joining a club with n people and they are choosing a committee of three. The committee also need to pick one of 6 colors as their uniform color. To calculate number of committees can be formed in different color, one way is $6*P(n+1,3)$, another ways is: 6C(n,2)+6C(n,3)(either 6*C(n,2), meaning I am in the committee, or 6C(n,3) meaning I am not in the committee. And use addition rule) Then we will have the equality, as desired. How is that?
– user48601
Commented Dec 19, 2013 at 1:31
• @Victoria: That’s very nice indeed. Commented Dec 19, 2013 at 1:31