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

39
0
Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2.
Not sure why you want to use induction to do this but here you go in a fast and loose manner:

Assume it's true for a set of size n. Examine a set of size n+1. Notice this set of size n+1 is just an n-set with a new element added to it. Call that new element 'A'. Now what does a 2-subset of the n+1-set look like? Either it has A or it doesn't. Thus, using our inductive hypothesis, we see there are:

[tex]\frac{n*(n-1)}{2} + n = \frac{(n+1)*n}{2}[/tex]

2-subsets. And that's exactly what we want to see.
 
256
0
you mean, considering a set of n elements the number of subsets with 2 elements obtained from that set is equal to n(n-1)/2?
 
256
0
if so, it is easy to see that the first combine with n-1 elements, the second with n-2 elements, and so on
 
841
0
if so, it is easy to see that the first combine with n-1 elements, the second with n-2 elements, and so on
Yes That gives a direct formula but what the poster needed was a step for an inductive proof which is what Rodigee gave since the new element (n+1) combines with the first n elements to form n more sets of two elements.
 
Last edited:

Related Threads for: Induction Proof

  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
2
Views
1K
Replies
1
Views
3K
Replies
8
Views
4K
  • Last Post
Replies
1
Views
1K
Top