# help...inductive proof???

• Feb 16th 2008, 08: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, 04: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 $\{a_1,...,a_n,a_{n+1}\}$. Now the 2-subsets of this set are those that contain $a_i,a_j$ where $1\leq i,j\leq n$ and there are $n(n-1)/2$ such sub-sets. Also any set involving $a_{n+1}$ and anything else is another 2-subset and there are $\{ a_1,a_{n+1}\}, ... \{a_n,a_{n+1}\}$ in total $n$ such sub-sets. In total, we have $n+n(n-1)/2 = n(n+1)/2$.