# help...inductive proof???

• Feb 16th 2008, 07:44 AM
memb3rme
help...inductive proof???
can someone help me how to prove this...?

Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2. [hint: Let x be any object of A and B=A-{x}. Then a 2-subset of A is either a 2-subset of B or a 1-subset of B. Count the number of subsets in each case.}

-Thanks
• Feb 16th 2008, 03:11 PM
ThePerfectHacker
Quote:

Originally Posted by memb3rme
can someone help me how to prove this...?

Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2. [hint: Let x be any object of A and B=A-{x}. Then a 2-subset of A is either a 2-subset of B or a 1-subset of B. Count the number of subsets in each case.}

-Thanks

The basic cases are trivial. Let $\displaystyle \{a_1,...,a_n,a_{n+1}\}$. Now the 2-subsets of this set are those that contain $\displaystyle a_i,a_j$ where $\displaystyle 1\leq i,j\leq n$ and there are $\displaystyle n(n-1)/2$ such sub-sets. Also any set involving $\displaystyle a_{n+1}$ and anything else is another 2-subset and there are $\displaystyle \{ a_1,a_{n+1}\}, ... \{a_n,a_{n+1}\}$ in total $\displaystyle n$ such sub-sets. In total, we have $\displaystyle n+n(n-1)/2 = n(n+1)/2$.