Induction Proof

  • Thread starter Ella087
  • Start date
  • #1
Ella087
3
0
Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2.
 

Answers and Replies

  • #2
Pere Callahan
586
1
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?
 
  • #3
mathman
Science Advisor
8,087
550
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.
 
  • #4
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).
 

Suggested for: Induction Proof

Replies
4
Views
624
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
8
Views
557
Replies
4
Views
3K
MHB Set proof
  • Last Post
Replies
5
Views
656
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
316
  • Last Post
Replies
1
Views
734
Replies
8
Views
447
  • Last Post
Replies
1
Views
2K
Top