- #1

sta|ker

- 12

- 0

## Homework Statement

Prove that a set with n elements has [itex]\frac{n(n-1)(n-2)}{6}[/itex] subsets containing exactly three elements whenever n is an integer greater than or equal to 3.

Our professor wants us to use Induction.

## Homework Equations

[itex]P(n) = \frac{n(n-1)(n-2)}{6}[/itex]

[itex]n \geq 3[/itex]

## The Attempt at a Solution

Since our professor wants to use Induction, I tried to prove the basis:

[itex]P(3)=\frac{3(2)(1)}{6} = \frac{6}{6} = 1[/itex]

This is true given any set (with elements equal to 3):

[itex]\{x_{1}, x_{2}, x_{3}\}[/itex] has subsets [itex]\{\{∅\},\{x_{1}\}, \{x_{2}\}, \{x_{3}\}, \{x_{1},x_{2}\}, \{x_{1},x_{3}\}, \{x_{2},x_{3}\},\{x_{1},x_{2},x_{3}\}\}[/itex]

So, from here I naturally tried to prove P(n+1). In this process, I'd try to find something to add to P(n) to equal P(n+1). With some guess work, I came up with the following:

[itex]\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2} = \frac{n(n+1)(n-1)}{6}[/itex].

I noticed (from an example in the textbook) that [itex]\frac{n(n-1)}{2}[/itex] is actually the formula that equates to the number of subsets that contain 2 elements. I'm assuming that this isn't a coincidence. The problem I have from here is: why can [itex]\frac{n(n-1)}{2}[/itex] be added to [itex]\frac{n(n-1)(n-2)}{6}[/itex]? Is there a rule or law I'm missing?