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

Printable View

- Mar 14th 2008, 03:47 PMst4rl1ightInduction Proof.........
Prove by induction that the number of 2-subsets of an n-set

**A**equals**n(n-1)/2**. - Mar 14th 2008, 09:48 PMroy_zhang
First please note that a 2-subset is a subset of a set on n elements containing exactly 2 elements, so the number of 2-subsets of an n-set is just . Now let's prove it by induction:

Base Step: When , it is trivial (we have 2-subset); when , we have 2-subset.

Inductive Step: Now lets assume when , we have 2-subsets. Consider the case when (i.e. we add one more element into the set, so how many**more**2-subsets will be introduced? The answer is**more**2-subsets are introduced. Think about this)

So the total number of 2-subsets when is , this competes the inductive step.

Roy