Induction to prove then number of subsets with elements of 3

[sta|ker]

Homework Statement

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.

Homework Equations

P(n) = \frac{n(n-1)(n-2)}{6}
n \geq 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?

 

[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?

 

[sta|ker]

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?

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]

 

[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.

 

[sta|ker]

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.

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...

 

[haruspex]

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...

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!

 

[sta|ker]

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!

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.

 

[haruspex]

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.

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

 

[sta|ker]

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

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?

 

[haruspex]

It won't change them, that's why I said b would be a+m.

Ok, but you did not make it clear that this is what you meant by a and m.

... and b can be represented by \frac{n(n-1)(n+1)}{6}.

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?

 

[sta|ker]

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?

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.

 

[haruspex]

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.

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?

 

[sta|ker]

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?

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?

 

[haruspex]

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?

That's it.

 

[sta|ker]

That's it.

Excellent, thank you very much for your patience!