Set example

Claim: If $n$ is a positive integer greater than or equal to 2, then a set with $n$ elements has $\dfrac{n(n-1)}{2}$ possible subsets of size 2. We will refer to this claim as $P(n)$.

Try it out

Suppose $n = 3$, and our set contains the elements $(a, b, c)$. There are 3 possible subsets of size 2: $(a, b)$, $(a, c)$, and $(b, c)$. We also have that $\dfrac{3(3-1)}{2} = 3$.

Induction proof

We wish to use mathematical induction to prove that $P(n)$ holds for all integers $n \geq 2$. That is, that a set with $n$ elements has $\dfrac{n(n-1)}{2}$possible subsets of size 2.

Base case

We must prove that $P(n)$ holds for the smallest such integer, $n = 2$. We must show that a set with two elements contains $\dfrac{2(2-1)}{2} = 1$ possible subsets of size 2. If a set has just two elements, then there is only one possible subset of size 2 – the subset that contains both elements. This proves $P(2)$, so the base case holds.

Inductive step

We assume the inductive hypothesis - that $P(k)$ holds for some arbitrary integer $k \geq 2$. In other words, we assume that a set with $k$ elements has $\dfrac{k(k-1)}{2}$ possible subsets of size 2. We must prove that $P(k+1)$ also holds – i.e., that a set with $k + 1$ elements has:

possible subsets of size 2.

Introducing a new element to a set with $k$ elements yields $k$ additional 2-element subsets, as the new element could pair with each of the original elements.

A set with $k+1$ elements contains all the original $\dfrac{k(k-1)}{2}$ size-2 elements from the size- $k$ set, plus the $k$ new subsets described above.

We have that:

We have proved $P(k+1)$. Thus the inductive hypothesis holds.

We conclude that for all positive integers $n \geq 2$, $P(n)$ holds – that is, that a set with $n$ elements has $\dfrac{n(n-1)}{2}$ possible subsets of size 2.