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