Proof by induction (using base case and inductive step)

Question

I'm struggling to write a proof for the following using proof by induction:

Let Y be a set of size $i$, where $i ∈ ℕ$. Prove: $$|\{X ⊆ Y: |X| = 2\}| = {i(i-1)\over 2}$$

How would I prove this using a base case and inductive step.

Answer 1

Induction step:

So you have now $i+1$ elements. Without Loss of Generality we may assume that $Y=\{1,2,3,…,i,i+1\}$ You can make ${i(i-1)\over 2}$ sets with 2 elements in a set with $i$ elements by I.H. Now how many two element sets we have with element $i+1$ in it?

Since we can pair $i+1$ with each element, we have $i$ such sets, so now you have $${i(i-1)\over 2}+i$$ such sets. OK?