Combinatoric Proof for choosing objects

[silvermane]

I've been tutoring students at my college this semester, and came across this problem with a student:

Show for all integers n$$\geq$$k$$\geq$$3,

nCk - (n-3)C(k-3) = (n-1)Ck + (n-2)C(k-1) +(n-3)C(k-2)

Since it's a combinatorial proof, I was looking at the number of ways that we could choose k colors to color a picture with, where we must have green, blue, and purple in our picture, or just 2 or 1 of them. (I want to be creative for her when I explain it)

Left Side:
Total ways to choose k colors from n colors is nCk.
The number of ways we wouldn't have them in our color choice is (n-3)C(k-3).

Right Side:
This is the side I'm having trouble figuring out. I don't know if my explanation is valid for the left side, but if anyone could help me out here, it would be great. I want to make sure I understand this for when I go to explain it to my tutee.

Thanks for your help in advance!

 

[JThompson]

I could be wrong, but I don't think that the color problem you chose works with $n-3\choose{k-3}$. This would be the number of ways in which we choose k colors while always choosing red, blue, and green- if you wanted to count the sets that don't include one of those colors (which is what it sounds like you intended), it would be $n-3\choose{k}$.

However, this could be the number of ways to color a picture with k colors without using all three of red, green, and blue. The right hand side could then be:
$$n-1\choose{k}$$- the number of ways to use k colors without using red

$$n-2\choose{k-1}$$- the number of ways to use k colors while using red but not using blue

$$n-3\choose{k-2}$$- the number of ways to use k colors while using red and blue but not using green

 

[silvermane]

I could be wrong, but I don't think that the color problem you chose works with $n-3\choose{k-3}$. This would be the number of ways in which we choose k colors while always choosing red, blue, and green- if you wanted to count the sets that don't include one of those colors (which is what it sounds like you intended), it would be $n-3\choose{k}$.

However, this could be the number of ways to color a picture with k colors without using all three of red, green, and blue. The right hand side could then be:
$$n-1\choose{k}$$- the number of ways to use k colors without using red

$$n-2\choose{k-1}$$- the number of ways to use k colors while using red but not using blue

$$n-3\choose{k-2}$$- the number of ways to use k colors while using red and blue but not using green

Yeah I just recently realized that it wouldn't work. That explains why I wasn't understanding how to apply my reasoning to the right-hand-side. I really like how you explained it too, if it's okay if I use this when going over it with my friend. I used to be so good at this too haha. Thank you so much for your help!

 

[JThompson]

No problem, and of course you can use the example.