1. ## Induction proof

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

2. Let me illustrate in a lazy way.

What we are being asked to do is choose 2 out of n. C(n,2).

$\frac{n!}{2!(n-2)!}=\frac{n(n-1)(n-2)(n-3).....}{2(n-2)(n-3)...}$

As you can see, everything cancels in the numerator and denominator except

$\frac{n(n-1)}{2}$

Check it, how many 2 subsets can be made from 10. C(10,2)=45

$\frac{10*9}{2}=45$

Now, we want to show an induction step.

$\frac{(n+1)!}{2!((n+1)-2)!}=\frac{(n+1)!}{2(n-1)!}$

$\frac{(n+1)(n)(n-1)(n-2)(n-3)......}{2(n-1)(n-2)(n-3).....}$

See what cancels this time?. Everything but $\frac{n(n+1)}{2}$

Note that $\frac{(n+1)((n+1)-1)}{2}=\frac{n(n+1)}{2}$

And it is shown.

3. Sorry Galactus, but I don’t think the question is asking us to assume any combinatorial formula at all. Here’s a more direct way.

First, check that the statement is true for $n=0$. Obviously the empty set can’t have any subset with 2 elements and $\frac{0(0-1)}{2}=0$ so that’s fine. (To be on the safe side, we might also check the case $n=1$, possibly even $n=2$, but I’m sure the inductive method below works by just assuming $n\geq0$.)

Now assume the statement is true for any set with n elements ( $n\geq0$). Consider a set A with $n+1$ elements and pick any element $a\in A$. (A contains at least 1 element.) Then $A\backslash\{a\}$ contains n elements. The number of 2-element subsets of A not containing a is just the number of 2-element subsets of $A\backslash\{a\}$, which by the inductive hypothesis is $\frac{n(n-1)}{2}$. The number of 2-element subsets of A which do contain a is n (i.e. a plus any of the other n elements of A). So:

no. of 2-element subsets of A = no. of 2-element subsets of A not containing a + no. of 2-element subsets of A containing a

$\color{white}.\hspace{45mm}.$ $=\ \frac{n(n-1)}{2}\quad+\quad n$

which you should find is equal to $\frac{(n+1)((n+1)-1)}{2}$.