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?
|{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$
FROM A PM
This is so puzzling because this is such a well know formula in another context.Originally Posted by inayat
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