1. ## Proof by induction

Let A be a set of size n, where n is an integer. Prove by induction that |{x ⊆ A | |x| = 2}| =n(n−1) / 2

Not sure how to approach this.

Would i be best assigning n with a value like 2?

2. ## Re: Proof by induction

For the base case, yes.

For the induction step notice that only one of the $n+1$ elements is "new", so you just add pairs that include that element to the total for the $|A|=n$.

3. ## Re: Proof by induction

Originally Posted by inayat
Let A be a set of size n, where n is an integer. Prove by induction that |{x ⊆ A | |x| = 2}| =n(n−1) / 2?
|{x ⊆ A | |x| = 2}| =n(n−1) / 2 That is the strangest notation I have seen. It took quite a while to come to a reasonable reading.
Does it mean that given a set of containing n elements then the cardinality of the collection of all subsets of the given set the contain two elements is $\dfrac{n(n-1)}{2}$.

Lets use some usual notation. $\|A\|=n$, i.e. the set $A$ has $n$ elements then $\|\{x\subseteq A| \|x\|=2\}\|=\dfrac{n(n-1)}{2}$
Suppose that $n=1$ so $\{x\subseteq A| \|x\|=2\}=\emptyset$, i.e. there can be no two element subsets.
So note $\dfrac{1(1-1)}{2}=0$ That proved the base case.

Now suppose $K>1~\&~\|A\|=K$ so that $\|\{x\subseteq A| \|x\|=2\}\|=\dfrac{K(K-1)}{2}$.
Try to move up to $\|A\|=K+1$

4. ## Re: Proof by induction

Originally Posted by inayat
Let A be a set of size n, where n is an integer. Prove by induction that |{x ⊆ A | |x| = 2}| =n(n−1) / 2
FROM A PM
Originally Posted by inayat
Thanks for the help on the thread i posted.
Would i be right to sub in K+1 into the original question? Not sure how to proceed.
This is so puzzling because this is such a well know formula in another context.
Here is where I left it: the statement is true for the base case $n=1$ Then comes an induction hypothesis, the statement is true for some $K>1$.
Now the goal is true for that $K+1$.
So we consider a set $B~\&~\|B\|=K+1$, Here is where the proof js unusual.
List the set $\{b_1,b_2,\cdots,b_K,b_{K+1}\}$. Remove the last element, $B'=\{b_1,b_2, \cdots,b_K \}$ contains $\dfrac{K(K-1)}{2}$ two-element subsets by the induction hypothesis. Form a new collection of two-element subsets $\mathcal{B}=\{\{b_1,b_{K+1}\},\{b_2,b_{K+1}\}, \cdots,\{b_K,b_{K+1}\}\}$

Take a moment to convince yourself that $\|\mathcal{B}\|=K$ Let $\mathcal{B}'$ be the collection of all two-elements of \mathcal{B} \begin{align*}\|\mathcal{B}'\|&=\|B'\|+K \\&=\dfrac{K(K-1)}{2}+K\\&=\dfrac{K(K-1)+2K}{2}\\&=\dfrac{(K^2+K)}{2}\\&=\dfrac{[K+1]K}{2}\\&=\dfrac{[K+1]([K+1]-1)}{2} \end{align*}\$
QED