# Induction Proof.........

• Mar 14th 2008, 03:47 PM
st4rl1ight
Induction 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 PM
roy_zhang
Quote:

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

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 $\binom{n}{2}=\frac{n(n-1)}{2}$. Now let's prove it by induction:

Base Step: When $n=1$, it is trivial (we have $\frac{1(1-1)}{2}=0$ 2-subset); when $n=2$, we have $\frac{2(2-1)}{2}=1$ 2-subset.

Inductive Step: Now lets assume when $n=k$, we have $\frac{k(k-1)}{2}$ 2-subsets. Consider the case when $n=k+1$ (i.e. we add one more element into the set, so how many more 2-subsets will be introduced? The answer is $k$ more 2-subsets are introduced. Think about this)
So the total number of 2-subsets when $n=k+1$ is $\frac{k(k-1)}{2}+k=\frac{(k+1)(k+1-1)}{2}$, this competes the inductive step.

Roy