0
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2019 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, 2019 at 17:13
  • $\begingroup$ @fleablood it needs to be inductive $\endgroup$ Nov 21, 2019 at 19:41

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
3
  • 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, 2019 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, 2019 at 19:46
  • $\begingroup$ Just make the set $Y_i = \{a_j, j=1\text{ to }i\}$. $\endgroup$ Nov 21, 2019 at 20:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .