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.

  • $\begingroup$ I've removed the "proof-theory" tag - it refers to a specific subfield of mathematical logic, not general questions about proofs. $\endgroup$ Nov 21 '19 at 17:13
  • $\begingroup$ 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. $\endgroup$
    – fleablood
    Nov 21 '19 at 17:13
  • $\begingroup$ @fleablood it needs to be inductive $\endgroup$ Nov 21 '19 at 19:41

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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Nov 21 '19 at 18:31
  • $\begingroup$ @aqua thanks for your reply, please could you explain it in more detail as I am slightly confused $\endgroup$ Nov 21 '19 at 19:46
  • $\begingroup$ Just make the set $Y_i = \{a_j, j=1\text{ to }i\}$. $\endgroup$ Nov 21 '19 at 20:00

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.