Induction to prove then number of subsets with elements of 3

[sta|ker]

Homework Statement

Prove that a set with n elements has [itex]\frac{n(n-1)(n-2)}{6}[/itex] 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

[itex]P(n) = \frac{n(n-1)(n-2)}{6}[/itex]
[itex]n \geq 3[/itex]

The Attempt at a Solution

Since our professor wants to use Induction, I tried to prove the basis:
[itex]P(3)=\frac{3(2)(1)}{6} = \frac{6}{6} = 1[/itex]

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

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:
[itex]\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2} = \frac{n(n+1)(n-1)}{6}[/itex].

I noticed (from an example in the textbook) that [itex]\frac{n(n-1)}{2}[/itex] 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 [itex]\frac{n(n-1)}{2}[/itex] be added to [itex]\frac{n(n-1)(n-2)}{6}[/itex]? 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:
[itex]n[/itex] subsets of 4 in [itex]A[/itex]

[itex]B = A \cup \{x_{4}\}[/itex]

[itex]A = \{x_{1}, x_{2}, x_{3}\}[/itex]

[itex]B = \{x_{1}, x_{2}, x_{3}, x_{4}\}[/itex]

So, [itex]n=1[/itex] for [itex]A[/itex], and [itex]n=4[/itex] (1 without [itex]x_{4}[/itex], 3 with [itex]x_{4}[/itex]).

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

 

[haruspex]

So:
[itex]n[/itex] subsets of 4 in [itex]A[/itex]

[itex]B = A \cup \{x_{4}\}[/itex]

[itex]A = \{x_{1}, x_{2}, x_{3}\}[/itex]

[itex]B = \{x_{1}, x_{2}, x_{3}, x_{4}\}[/itex]

So, [itex]n=1[/itex] for [itex]A[/itex], and [itex]n=4[/itex] (1 without [itex]x_{4}[/itex], 3 with [itex]x_{4}[/itex]).

The only pattern I see here is that there are 3 elements in [itex]A[/itex] and 3 subsets with [itex]x_{4}[/itex] in [itex]B[/itex]. 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 [itex]A[/itex] as a set with [itex]n[/itex] subsets of size 3. If we add one more element, and set it to [itex]B[/itex], we can say [itex]B[/itex] is a set with [itex]n + m[/itex] subsets of size 3. So, if we say the total size of [itex]A[/itex]'s subsets of size 3 is [itex]a = n[/itex], then we can say the total size of [itex]B[/itex]'s subsets of size 3 is [itex]b = a + m[/itex]. I guess we can say [itex]m = a - b[/itex] or [itex]m = n - b[/itex], but I still don't know what [itex]b[/itex] is or [itex]m[/itex] is.

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

 

[haruspex]

Alright, so we declare [itex]A[/itex] as a set with [itex]n[/itex] subsets of size 3. If we add one more element, and set it to [itex]B[/itex], we can say [itex]B[/itex] is a set with [itex]n + m[/itex] subsets of size 3. So, if we say the total size of [itex]A[/itex]'s subsets of size 3 is [itex]a = n[/itex], then we can say the total size of [itex]B[/itex]'s subsets of size 3 is [itex]b = a + m[/itex]. I guess we can say [itex]m = a - b[/itex] or [itex]m = n - b[/itex], but I still don't know what [itex]b[/itex] is or [itex]m[/itex] 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 [itex]b[/itex] would be [itex]a+m[/itex]. [itex]a[/itex] is [itex]n[/itex] and [itex]m[/itex] 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 [itex]a[/itex] represent the amount of subsets with 3 elements in the set [itex]A[/itex].
Let [itex]b[/itex] represent the amount of subsets with 3 elements in the set [itex]B[/itex].

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

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

So, if we rework [itex]b = a + c[/itex], we get [itex]c = b - a[/itex]. Substituting our formulas, we get:

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

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

Would this be considered a valid proof?

 

[haruspex]

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

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

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

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:

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

This means [itex]b = a + c[/itex].

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

The only thing I can come up with is that [itex]c=b-a[/itex].

 

[haruspex]

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

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

This means [itex]b = a + c[/itex].

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

The only thing I can come up with is that [itex]c=b-a[/itex].

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 [itex]c[/itex] by taking all the subsets with 2 elements in [itex]A[/itex] and adding the extra element from [itex]B[/itex]. So essentially [itex]c[/itex] is the number of subsets with 2 elements in [itex]A[/itex].

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

[itex]\frac{n(n-1)(n+1)}{6} = \frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}[/itex], which is true.

This accurate? Or did I miss it again?

 

[haruspex]

Alright, I think I have it:

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

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

[itex]\frac{n(n-1)(n+1)}{6} = \frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}[/itex], 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!