Proof of n(n-1)/2 as the Number of 2-Subsets in an n-Set

  • Thread starter Ella087
  • Start date
  • Tags
    Proof
In summary, the number of 2-subsets of an n-set A can be proven to be equal to n(n-1)/2 using induction. By examining a set of size n+1 and using the inductive hypothesis for a set of size n, it can be shown that there are n more sets of two elements created when a new element is added to the set. This results in a total of n(n-1)/2 + n = (n+1)*n/2 2-subsets.
  • #1
Ella087
3
0
Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2.
 
Physics news on Phys.org
  • #2
Ella087 said:
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.
 
  • #3
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?
 
  • #4
if so, it is easy to see that the first combine with n-1 elements, the second with n-2 elements, and so on
 
  • #5
al-mahed said:
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:

FAQ: Proof of n(n-1)/2 as the Number of 2-Subsets in an n-Set

What is the formula for calculating the number of 2-subsets in an n-set?

The formula for calculating the number of 2-subsets in an n-set is n(n-1)/2, where n is the number of elements in the set.

How is this formula derived?

This formula is derived from the combination formula, n choose 2, which is represented as nC2. The formula for nC2 is n!/(2!(n-2)!). By simplifying this expression, we get n(n-1)/2.

Can you provide an example to demonstrate this formula?

Sure. Let's say we have a set of 5 elements: {1, 2, 3, 4, 5}. The number of 2-subsets in this set would be calculated as 5(5-1)/2 = 10. The 2-subsets would be: {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}.

What is the significance of this formula in mathematics?

This formula is significant because it helps us calculate the number of combinations or subsets of a given size in a set. It is also used in various combinatorial problems and has applications in fields such as probability, statistics, and computer science.

Are there any limitations to this formula?

Yes, this formula only applies to finding the number of 2-subsets in a set. It cannot be used to find the number of subsets of any other size or to find the number of permutations in a set. Additionally, this formula assumes that all elements in the set are distinct and cannot be repeated.

Similar threads

Back
Top