- 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**.- Thread starter Ella087
- Start date

- 3

- 0

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

- 39

- 0

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

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

- 256

- 0

- 841

- 0

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:

- 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