I need to prove by induction that
the number of 2-elements subset of an n elements set is $\frac{n(n-1)}{2}$
I am stuck on where I should start from and how should I solve this.
I am guessing that I should begin with something like this:
${0 \choose 2} +{1 \choose 2}+{2 \choose 2} +...+{n \choose 2}$ = $\frac{n(n-1)}{2} $
step 1. let $n = 1$
${0 \choose 2} + {1 \choose 2} = \frac{1(1-1)}{2}$
$0 = 0$
True for $n = 1$
step 2. assume $n = k$
${0 \choose 2} +{1 \choose 2}+{2 \choose 2} +...+{k \choose 2}$ = $\frac{k(k-1)}{2}$
step 3. let $n = k+1$
${0 \choose 2} +{1 \choose 2}+{2 \choose 2} +...+{k \choose 2} + {k+1 \choose 2}$ = $\frac{k+1(k+1 - 1)}{2}$
from step 2, ${0 \choose 2} +{1 \choose 2}+{2 \choose 2} +...+{k \choose 2}$ = $\frac{k(k-1)}{2}$
so
$\frac{k(k-1)}{2}$ + ${k+1 \choose 2}$ = $\frac{k+1(k+1 - 1)}{2}$
and I am not sure what I should do from here or whether I am on the right track.
can someone clear me out please?
The sum of binomial coefficients you are using is not correct. Try this instead.
If $n=0$ or $n=1$, then there are no 2-element subsets. Also, in both cases $\frac{n(n-1)}{2}=0$. Now assume that the statement is true for some $n\ge 1$, and consider a set $X$ of size $n+1$. Choose a fixed element $x$ of $X$. Then, by the induction hypothesis there are $\frac{n(n-1)}{2}$ 2-element subsets of $X$ that do not contain $x$. There are also $n$ 2-element subsets that contain $x$, by pairing $x$ with each other element of $X$. In total, that gives $$\frac{n(n-1)}{2}+n=\frac{n(n-1)}{2}+\frac{2n}{2}=\frac{(n+1)n}{2}$$ 2-element subsets of $X$, as required.