# Math Help - Subsets

1. ## Subsets

Let $\binom{n}{r}$ stand for the number of subsets of size r taken from a set of size n. (This is the number of ways of choosing r objects from n if the order does not matter.) Every subset of the set 1, 2, . . . , n either contains the element 1 or it doesn’t. By considering these two
possibilities, show that:

$\binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}$

By using a similar method or otherwise, prove that:

$\binom{n-2}{r-2} + 2\binom{n-2}{r-1} + \binom{n-2}{r} = \binom{n}{r}$

I'm not sure what to do. I do not understand the queston, with what they said in the 1st paragraph and how to apply it here. Can i basically use the idea of binomial coefficients and factorials, and simplify the fraction or what?

Thanks for the help

2. Originally Posted by Aquafina
Let $\binom{n}{r}$ stand for the number of subsets of size r taken from a set of size n. (This is the number of ways of choosing r objects from n if the order does not matter.) Every subset of the set 1, 2, . . . , n either contains the element 1 or it doesn’t. By considering these two
possibilities, show that:

$\binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}$

By using a similar method or otherwise, prove that:

$\binom{n-2}{r-2} + 2\binom{n-2}{r-1} + \binom{n-2}{r} = \binom{n}{r}$

I'm not sure what to do. I do not understand the queston, with what they said in the 1st paragraph and how to apply it here. Can i basically use the idea of binomial coefficients and factorials, and simplify the fraction or what?

Thanks for the help
Take the first equation. You are asked to count the subsets of size r of a set of size n in two different ways: on the right side you count the subsets of size r. On the left side of the equation, you count the subsets of size r that contain 1 and then add to that the number of subsets of size r that do not contain 1, which also gives you the number of subsets of size r. Hence equality holds.

This method of counting the same thing two ways to show that an equation holds is quite frequently used in combinatorics. It's called the "counting two ways" method of proof (you guessed it, I suppose).

Now try to guess what the left side of the second equation may be counting. From the right side you get the hint that it is probably also a somewhat complicated way of counting all the subsets of size r of a set of size n.

* I dont know why my latex symbols are not showing...*
They are not showing because you need to wrap them in $[$math $]$ ... $[$/math $]$ tags.

3. Originally Posted by Failure
Take the first equation. You are asked to count the subsets of size r of a set of size n in two different ways: on the right side you count the subsets of size r. On the left side of the equation, you count the subsets of size r that contain 1 and then add to that the number of subsets of size r that do not contain 1, which also gives you the number of subsets of size r. Hence equality holds.

This method of counting the same thing two ways to show that an equation holds is quite frequently used in combinatorics. It's called the "counting two ways" method of proof (you guessed it, I suppose).

Now try to guess what the left side of the second equation may be counting. From the right side you get the hint that it is probably also a somewhat complicated way of counting all the subsets of size r of a set of size n.
Hi thanks.

So when I evaluate the LHS and the RHS, do I have to treat them like binomial coefficients?

like n!/(r!(n-r)!) ?

4. Originally Posted by Aquafina
Hi thanks.

So when I evaluate the LHS and the RHS, do I have to treat them like binomial coefficients?
Yes, but with their combinatorial interpretation. Thus $\binom{n}{r}$ is the number of subsets of size r of a set of size n.
Of course, it would be possible to do everything as an exercise in algebra, but that would not be an elegant way of proving that the equation holds. Furthermore, the method of "counting two ways" is best tried out first on such relatively simple cases, even though a purely algebraic argument could be made instead.

like n!/(r!(n-r)!) ?
No, not at all! (Except if you want to do the proof purely algebraically, i.e. not by the method of "counting two ways".) - You use the combinatorial interpretation of the binomial coefficient as the total number of r-element subsets of an n-element set. Thus, if you want to count how many subsets of size r containing the element 1 of a set of n elements (that contains 1) there are, you find that, using the combinatorial interpretation of the binomial coefficient, there are $\binom{n-1}{r-1}$ such subsets. - Why? - Because, since 1 is to be an element of such a subset, you are only allowed to add r-1 other elements from the n-1 remaining elements (i.e. excluding 1) of the superset to that subset you are trying to "construct" (in your mind, that is). ... and so on.