$2$-element subsets of $n$ elements?

Question

the question is as follows:

Give a recursive definition for the number of $2$-element subsets of $n$ elements.

We started working this out in class and here is where we got too:

-if $n = 0$, then we are looking for the $2$-element subsets of $0$ elements. There are none. So $f(0) = 0.$

-If $ n > 0$, then our set looks like $S $= {$s_1, s_2, ..., s_n$}. Let's look at all of the $2$-element subsets of $S$.

1. Some of them will include $s_n$. These sets look like {$x, s_n$}, where x is one of the elements {$s_1, s_2, ..., s_{n-1}$}. As we have $n-1$ choices for the element $x$, we have $n+1$ 2-element subsets that contain sn.
2. Others will not include sn. But if they don't, then we are looking for the $2$-element subsets of {$s_1, s_2, ..., s_{n-1}$}, and we know that there are $f(n-1)$ of these.

I know the recursive definition is:

$f(0) = 0$

$f(n) = f(n-1)+n-1$

But I don't really understand what a 2 element subset is. Can someone give me an example of this/more insight into this problem? What are we really trying to show here? Also why isn't $f(1)$ equal to $0$ as $f(0) = 0$ since both of them are less than $2$?

Answer 1

A $2$ elelment subset means, a subset which has cardinality $2$. So if $n>0$, and you have $S$={$s_1,s_2...s_n$}.

$f(1)=0$ as said by taninamdar above in comment. Now to find $f(n)$, mark the last element i.e. $s_n$ (or mark any element, does not make any diffrence so no generality lost here). Now for time being keep $s_n$ out of the picture, and only consider the set $X$={$s_1,s_2,....s_{n-1}$}. Now number of $2$ element subsets from $X$ are $f(n-1)$ and every $2$ element subset of $X$ is also a $2$ element subset of $S$. so all $f(n-1)$ are getting counted, and none of the $2$ element subsets of $X$ will have $s_n$ as the whole set does not have it. Now we only need to count those $2$ element subsets of $S$ which include $s_n$, So fixing one element as $s_n$ out of $2$ elements leave only one choice to pick another element from {$s_1,.....s_{n-1}$}, and for that we have $n-1$ ways. so in total we have $f(n-1)+n-1$ $2$ element subsets.

Answer 2

A set of $n$ elements has ${n \choose 2}$ subsets of $2$ elements, where ${n \choose 2}$ is the binomial coefficient $n$ choose $2$.

By definition : $${n \choose 2} = \frac{n!}{2!(n-2)!} = \frac{n\cdot(n-1)}{2}$$

and by a well known theorem $$ \sum_{k=1}^{n-1} k = 1 + 2 + \dots + (n-1) = \frac{n\cdot(n-1)}{2} $$

The recursion the follows immediately.