Induction Proof

  • Thread starter Ella087
  • Start date
3
0

Main Question or Discussion Point

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

Answers and Replies

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
Science Advisor
7,716
398
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
268
6
Is it for learning induction proofs? Straightway, the number of selection of 2 distinct elements from n distinct elements is nC2 (= n combination 2).
 

Related Threads for: Induction Proof

  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
582
Replies
7
Views
1K
Replies
2
Views
1K
  • Last Post
Replies
4
Views
72K
Top