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$?

  • 2
    $\begingroup$ Note that $f(1) = f(0) + 1-1 = 0$ by second condition. $\endgroup$ – taninamdar Oct 7 '14 at 18:38

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.