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.

 

[blue_raver22]

I would approach this problem by breaking it down into simpler parts and using the fundamental principles of combinatorics. Firstly, let's consider the left side of the equation:

nCk - (n-3)C(k-3)

This represents the number of ways to choose k objects from a set of n objects, minus the number of ways to choose k-3 objects from a set of n-3 objects. This can be thought of as choosing k objects from the n objects, minus the cases where we do not have the required three colors (green, blue, and purple) in our selection. This can also be visualized as choosing k objects from a set of n-3 objects, and then adding back the three required colors.

Now, let's look at the right side of the equation:

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

This can be thought of as choosing k objects from a set of n-1 objects, plus choosing k-1 objects from a set of n-2 objects, plus choosing k-2 objects from a set of n-3 objects. This can also be visualized as choosing k objects from a set of n-1 objects, and then adding one more object from the remaining n-2 objects, and then adding one more object from the remaining n-3 objects.

To see how these two sides are equal, we can think about the process of choosing k objects from a set of n objects, while ensuring that we have at least one of the required colors (green, blue, and purple). On the left side, we subtract the cases where we do not have the required colors, and on the right side, we add the cases where we have one or more of the required colors. This results in the same total number of ways to choose k objects while ensuring that we have at least one of the required colors.

In summary, the left side represents choosing k objects from a set of n objects while ensuring we have at least one of the required colors, and the right side represents the same process but broken down into simpler steps. Therefore, both sides are equal and we have a combinatorial proof for the given equation.