0
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Yes, thanks for reminding. $\endgroup$
    – user48601
    Commented Dec 19, 2013 at 1:06
  • 1
    $\begingroup$ Just a note, this is an example where things are the other way round, the algebraic proof is trivial. $\endgroup$ Commented Dec 19, 2013 at 1:09
  • $\begingroup$ 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. $\endgroup$
    – user48601
    Commented Dec 19, 2013 at 1:13

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Oh, it's you again, thanks for the answer! $\endgroup$
    – user48601
    Commented Dec 19, 2013 at 1:19
  • $\begingroup$ 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.. $\endgroup$
    – user48601
    Commented Dec 19, 2013 at 1:20
  • $\begingroup$ @Victoria: You’re welcome! Feel free to leave a comment if you get stuck. $\endgroup$ Commented Dec 19, 2013 at 1:21
  • $\begingroup$ 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? $\endgroup$
    – user48601
    Commented Dec 19, 2013 at 1:31
  • $\begingroup$ @Victoria: That’s very nice indeed. $\endgroup$ Commented Dec 19, 2013 at 1:31

You must log in to answer this question.