Prove that a set having $n\geq 2$ elements has $\frac{n(n-1)}{2}$ subsets having exactly two elements.

Question

I want to prove this by induction. I have everything up to proving $k+1$. I know I want to show that a set having $k+1$ elements has $\frac{k(k+1)}{2}$ but I'm struggling to find the beginning step for this. Any help would be appreciated.

Answer 1

In order to use the induction hypothesis, you can think about isolating an element, name it $a$, in your set, call it $E$, containing $k+1$ elements.

Then $E\setminus\{a\}$ has, by the induction hypothesis, $\frac{k(k-1)}2$ subsets having exactly two elements, and you must add the number of subsets of $E$ having two elements, one of which is $a$. There are $k$ such subsets. All in all, the number of subsets of $E$ having exactly two elements is: $$\frac{k(k-1)}2+k=\frac{(k+1)k}2$$ which is what we wanted.

Answer 2

Hint: What is the meaning of the following binomial $\binom{n}{2}$?