1. ## 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

2. 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$.