1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction to prove then number of subsets with elements of 3

  1. Oct 15, 2013 #1
    1. The problem statement, all variables and given/known data
    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.

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


    3. 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?
     
  2. jcsd
  3. Oct 15, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  4. Oct 15, 2013 #3
    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
  5. Oct 16, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  6. Oct 16, 2013 #5
    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...
     
  7. Oct 16, 2013 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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!
     
  8. Oct 16, 2013 #7
    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.
     
  9. Oct 16, 2013 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    If you don't use the element that you added to A, how will it change the count of subsets?
     
  10. Oct 16, 2013 #9
    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?
     
  11. Oct 16, 2013 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  12. Oct 16, 2013 #11
    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].
     
  13. Oct 16, 2013 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  14. Oct 16, 2013 #13
    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?
     
  15. Oct 17, 2013 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That's it.
     
  16. Oct 17, 2013 #15
    Excellent, thank you very much for your patience! :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Induction to prove then number of subsets with elements of 3
  1. Proving a subset (Replies: 4)

Loading...