# Proof by induction (using base case and inductive step)

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.

• I've removed the "proof-theory" tag - it refers to a specific subfield of mathematical logic, not general questions about proofs. Nov 21 '19 at 17:13
• For clarification; do you specifically want an inductive proof or do you want any proof? I think a direct proof is easier and more convincing. Nov 21 '19 at 17:13
• @fleablood it needs to be inductive Nov 21 '19 at 19:41

## 1 Answer

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?

• You should include the phrase "Without Loss of Generality we may assume that $Y=\{1,2,3,\dots,i,i+1\}$" Otherwise, there is no reason to assume that the set actually has "element $i+1$" in it since the statement is about all possible sets with $i$ elements. Nov 21 '19 at 18:31
• @aqua thanks for your reply, please could you explain it in more detail as I am slightly confused Nov 21 '19 at 19:46
• Just make the set $Y_i = \{a_j, j=1\text{ to }i\}$. Nov 21 '19 at 20:00