Proving 2-Subsets of an n-Set A Equals n(n-1)/2

[Ella087]

Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2.

 

[Pere Callahan]

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?

 

[mathman]

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.

 

[ssd]

Is it for learning induction proofs? Straightway, the number of selection of 2 distinct elements from n distinct elements is nC2 (= n combination 2).