# Induction to prove then number of subsets with elements of 3

1. Oct 15, 2013

### sta|ker

1. The problem statement, all variables and given/known data
Prove that a set with n elements has $\frac{n(n-1)(n-2)}{6}$ subsets containing exactly three elements whenever n is an integer greater than or equal to 3.

Our professor wants us to use Induction.

2. Relevant equations
$P(n) = \frac{n(n-1)(n-2)}{6}$
$n \geq 3$

3. The attempt at a solution
Since our professor wants to use Induction, I tried to prove the basis:
$P(3)=\frac{3(2)(1)}{6} = \frac{6}{6} = 1$

This is true given any set (with elements equal to 3):
$\{x_{1}, x_{2}, x_{3}\}$ has subsets $\{\{∅\},\{x_{1}\}, \{x_{2}\}, \{x_{3}\}, \{x_{1},x_{2}\}, \{x_{1},x_{3}\}, \{x_{2},x_{3}\},\{x_{1},x_{2},x_{3}\}\}$

So, from here I naturally tried to prove P(n+1). In this process, I'd try to find something to add to P(n) to equal P(n+1). With some guess work, I came up with the following:
$\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2} = \frac{n(n+1)(n-1)}{6}$.

I noticed (from an example in the textbook) that $\frac{n(n-1)}{2}$ is actually the formula that equates to the number of subsets that contain 2 elements. I'm assuming that this isn't a coincidence. The problem I have from here is: why can $\frac{n(n-1)}{2}$ be added to $\frac{n(n-1)(n-2)}{6}$? Is there a rule or law I'm missing?

2. Oct 15, 2013

### haruspex

Suppose you have a list of the subsets of 3 elements of some set A. Now you add a new element to A. How many subsets of 3 are t here in the expanded set that do not include the new element? How many are there that do include the new element?

3. Oct 15, 2013

### sta|ker

EDIT 2: Ok, just re-read again. So there are 3 sets of 3 in the extended set (lets call this B) that contain the new element, and 1 that doesn't. I'm still not sure of the relevance. I actually just re-read my assignment and our professor wants us to use Structural Induction, which is extremely confusing here.

[STRIKE]EDIT: I misread that (there's 1 subset of 3 in the first, and 3 subsets of 3 in the second). I still don't understand what's being implied though.[/STRIKE]

[STRIKE]Hmm, well, that would be 7 in set A, and if we make set B the set with the 4th element, that would be 7 without the 4th element, and 7 without the first 3. I still don't think I understand how that relates to this.[/STRIKE]

Last edited: Oct 15, 2013
4. Oct 16, 2013

### haruspex

To do the inductive step you need to work more generally. Suppose there are n 3-sets in A. We add one element x to form B. How many 3-sets are there in B which do not use x? How many do use x? When you have answered those the relevance will be quite clear.

5. Oct 16, 2013

### sta|ker

So:
$n$ subsets of 4 in $A$

$B = A \cup \{x_{4}\}$

$A = \{x_{1}, x_{2}, x_{3}\}$

$B = \{x_{1}, x_{2}, x_{3}, x_{4}\}$

So, $n=1$ for $A$, and $n=4$ (1 without $x_{4}$, 3 with $x_{4}$).

The only pattern I see here is that there are 3 elements in $A$ and 3 subsets with $x_{4}$ in $B$. Though I don't think that's a correct correlation...

6. Oct 16, 2013

### haruspex

No, you must do it with an arbitrary set A, not just a set of three elements. Don't try to ask what A looks like, just accept that it has n subsets of size 3. If you add an element but don't use it, how many subsets of size 3 can you make? The answer is extremely simple!

7. Oct 16, 2013

### sta|ker

Alright, so we declare $A$ as a set with $n$ subsets of size 3. If we add one more element, and set it to $B$, we can say $B$ is a set with $n + m$ subsets of size 3. So, if we say the total size of $A$'s subsets of size 3 is $a = n$, then we can say the total size of $B$'s subsets of size 3 is $b = a + m$. I guess we can say $m = a - b$ or $m = n - b$, but I still don't know what $b$ is or $m$ is.

I'm sorry, I don't mean to be a pain, but I'm just not seeing it.

8. Oct 16, 2013

### haruspex

If you don't use the element that you added to A, how will it change the count of subsets?

9. Oct 16, 2013

### sta|ker

It won't change them, that's why I said $b$ would be $a+m$. $a$ is $n$ and $m$ is the number of subsets that do contain the new element. If you don't use the added element, it isn't going to change the amount of subsets with 3 elements. Regardless, it gave me an idea:

Let $a$ represent the amount of subsets with 3 elements in the set $A$.
Let $b$ represent the amount of subsets with 3 elements in the set $B$.

We know that $A \subset B$, so we can declare: $b = a + c$ where $c$ is the count of all subsets with 3 elements in $B$ that do contain the added element.

We also know that $a$ can be represent by $\frac{n(n-1)(n-2)}{6}$ and $b$ can be represented by $\frac{n(n-1)(n+1)}{6}$.

So, if we rework $b = a + c$, we get $c = b - a$. Substituting our formulas, we get:

$c = \frac{n(n-1)(n+1)}{6} - \frac{n(n-1)(n-2)}{6}$. This ultimately ends up becoming $c = \frac{n(n-1)}{2}$. If we add that to $P(n)$ to attempt to obtain $P(n+1)$, it will result in an equal equation.

This is all given that $P(n) = \frac{n(n-1)(n-2)}{6}$ for $n \geq 3$, and that the base $P(3) = 1$, which is true, which implies $P(n+1)$.

Would this be considered a valid proof?

10. Oct 16, 2013

### haruspex

Ok, but you did not make it clear that this is what you meant by a and m.
No! That is what you are trying to prove, so you cannot assume it.
Think now about about how you would make a 3-subset of B that does use the added element. You have the added element in the 3-set... what else do you need in it?

11. Oct 16, 2013

### sta|ker

Hmm, I'm not sure I'm understanding this correctly:

$a$ represents the number of subsets containing 3 elements in a set A.
$b$ represents the number of subsets containing 3 elements in a set B.
$B$ is basically $A$ with an added element, so $B = A \cup \{x\}$
This means $A \subset B$, so there is a number we'll call $c$ that represents the subsets of 3 containing the added element.

This means $b = a + c$.

Now, given all this, are you asking what $c$ (the representative of the number of subsets with 3 elements in $B$ that contain the new element) is?

The only thing I can come up with is that $c=b-a$.

12. Oct 16, 2013

### haruspex

I don't think I can put it more clearly than I did in the last sentence of my previous post, short of giving you the answer.
Imagine you are constructing a set of 3 elements from B. You are required to use the added element that was not in A. What else do you need to complete the 3-set you are constructing? How many ways are there of doing that?

13. Oct 16, 2013

### sta|ker

Alright, I think I have it:

We can obtain $c$ by taking all the subsets with 2 elements in $A$ and adding the extra element from $B$. So essentially $c$ is the number of subsets with 2 elements in $A$.

From a previous problem, we know the number of subsets containing 2 elements in a set is calculated using $\frac{n(n-1)}{2}$. So, by assigning that to $c$, assigning $\frac{n(n-1)(n-2)}{6}$ to $a$ and $\frac{n(n-1)(n+1)}{6}$ to b, we can plug these equations into $b = a + c$, getting:

$\frac{n(n-1)(n+1)}{6} = \frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}$, which is true.

This accurate? Or did I miss it again?

14. Oct 17, 2013

### haruspex

That's it.

15. Oct 17, 2013

### sta|ker

Excellent, thank you very much for your patience!