1. Not finding help here? Sign up for a free 30min 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 Proof

  1. Mar 14, 2008 #1
    Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2.
     
  2. jcsd
  3. Mar 15, 2008 #2
    Can you count the number of 2-subsets of a set A with 1 element..? Well, it's obviously zero..what if A has two elements.... then there is one 2-subset, A itself ... what about three...? Can you relate the number of 2-subsets of a 3-set to the number of 2-subsets of a 2-set?

    Say the 2-set is A= {1,2} and the three set is B={1,2,3}. A 2-subset of A is certainly also a 2-subset of B, so you have {1,2}, but there are more 2-subsets of B, those containing 3. What can you pair 3 with? Apparently with any of the elements of A, which gives you another two 2-subsets of B, namely {1,3},{2,3}.

    So in total there are three 2-subsets of a set B with three elements, in agreement with your formula.

    Can you generalize this?
     
  4. Mar 15, 2008 #3

    mathman

    User Avatar
    Science Advisor
    Gold Member

    The n to n+1 case is rather simple. Assume for n we have n(n-1)/2 2-subsets. Add one more element. This adds n more two-subsets. n(n-1)/2 + n=n(n+1)/2.
     
  5. Mar 30, 2008 #4

    ssd

    User Avatar

    Is it for learning induction proofs? Straightway, the number of selection of 2 distinct elements from n distinct elements is nC2 (= n combination 2).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Induction Proof
  1. A Proof by induction (Replies: 4)

  2. Proof By Induction (Replies: 0)

Loading...