1. ## Set theory Puzzle

Let $\displaystyle S=\left\{1,2,\cdots,n\right\}$. It is quite commonly known that the number of subsets one can form from $\displaystyle S$ are $\displaystyle 2^n$, but how many pairs $\displaystyle A,B$ of these subsets is $\displaystyle A\subseteq B$ true?

2. Interesting,

So we're interested in finding all pairs $\displaystyle (A,B)\in n\times n$ such that $\displaystyle A\subseteq B$

Let $\displaystyle A\in \mathcal{P}(n)$ a set with $\displaystyle k$ elements. Then we have $\displaystyle \sum_{i=0}^{n-k}{n-k\choose i}= 2^{n-k}$ sets $\displaystyle B\in \mathcal{P}(n)$ such that $\displaystyle A\subseteq B$. Namely these are all sets, disjunct with $\displaystyle A$, we can unite $\displaystyle A$ with such that $\displaystyle A\cup B \in \mathcal{P}(n)$.

Thus the total amount of such pairs are: $\displaystyle \sum_{k=0}^{n}{n\choose k}2^{n-k} = (1+2)^n = 3^n$. With the Binomium of Newton.

3. Originally Posted by Dinkydoe
Interesting,

So we're interested in finding all pairs $\displaystyle (A,B)\in n\times n$ such that $\displaystyle A\subseteq B$

Let $\displaystyle A\in \mathcal{P}(n)$ a set with $\displaystyle k$ elements. Then we have $\displaystyle \sum_{i=0}^{n-k}{n-k\choose i}= 2^{n-k}$ sets $\displaystyle B\in \mathcal{P}(n)$ such that $\displaystyle A\subseteq B$. Namely these are all sets, disjunct with $\displaystyle A$, we can unite $\displaystyle A$ with such that $\displaystyle A\cup B \in \mathcal{P}(n)$.

Thus the total amount of such pairs are: $\displaystyle \sum_{k=0}^{n}{n\choose k}2^{n-k} = (1+2)^n = 3^n$. With the Binomium of Newton.
How much math must I learn to understand this? Am I hopeless?

4. How much math must I learn to understand this? Am I hopeless?
Not much really, it's pretty elementary. You've seen the induction proof of $\displaystyle |\mathcal{P}(n)| = 2^n$.

However this can fairly easily shown by applying the binomium of Newton too!
Observe that $\displaystyle |\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n}$.

Namely: it's how many different ways we can choose 0 elements, + how many different ways we can choose 1 element...etc.

However note that $\displaystyle 2^n = (1+1)^n$. Applying the binomium of newton: $\displaystyle (x+y)^n = \sum_{k=1}^{n}{n \choose k}x^ky^{n-k}$ with $\displaystyle x= y = 1$.

And this gives: $\displaystyle |\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n} = (1+1)^n = 2^n$.

That idea is used here again here.
Taking an element $\displaystyle A\in \mathcal{P}(n)$ with $\displaystyle k$ elements. How many sets $\displaystyle B\in \mathcal{P}(n)$ exist such that $\displaystyle A\subseteq B$? Well, we have $\displaystyle k$ elements in $\displaystyle A$. So we have $\displaystyle n-k$ elements left to choose from. Observe that the amount of such $\displaystyle B$'s equals the amount of subsets we can create from $\displaystyle n-k$ elements!

Hence there exists $\displaystyle 2^{n-k}$ of such B's in $\displaystyle \mathcal{P}(n)$.

Since we have $\displaystyle {n \choose k}$ elements in $\displaystyle \mathcal{P}(n)$ of length $\displaystyle k$, it follows we have $\displaystyle {n\choose k}2^{n-k}$ pairs $\displaystyle (A,B)\in \mathcal{P}(n)\times \mathcal{P}(n)$, where $\displaystyle A$ is a set of length $\displaystyle k$ and $\displaystyle A\subseteq B$.

Now we only need to sum over all different lengths $\displaystyle k$ a set $\displaystyle A$ can have. Thus we obtain:

Total amount of pairs $\displaystyle (A,B)$ = $\displaystyle \sum_{k=0}^{n}{n\choose k}2^{n-k}$.

And if we analyse this number close we can recognise the binomium of Newton again with $\displaystyle x= 1, y = 2$.

Hence we obtain: Total amount of pairs $\displaystyle (A,B) = 3^n$

5. Originally Posted by Dinkydoe
Not much really, it's pretty elementary. You've seen the induction proof of $\displaystyle |\mathcal{P}(n)| = 2^n$.

However this can fairly easily shown by applying the binomium of Newton too!
Observe that $\displaystyle |\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n}$.

Namely: it's how many different ways we can choose 0 elements, + how many different ways we can choose 1 element...etc.

However note that $\displaystyle 2^n = (1+1)^n$. Applying the binomium of newton: $\displaystyle (x+y)^n = \sum_{k=1}^{n}{n \choose k}x^ky^{n-k}$ with $\displaystyle x= y = 1$.

And this gives: $\displaystyle |\mathcal{P}(n)| = {n\choose 0}+{n\choose 1}+\cdots + {n\choose n} = (1+1)^n = 2^n$.

That idea is used here again here.
Taking an element $\displaystyle A\in \mathcal{P}(n)$ with $\displaystyle k$ elements. How many sets $\displaystyle B\in \mathcal{P}(n)$ exist such that $\displaystyle A\subseteq B$? Well, we have $\displaystyle k$ elements in $\displaystyle A$. So we have $\displaystyle n-k$ elements left to choose from. Observe that the amount of such $\displaystyle B$'s equals the amount of subsets we can create from $\displaystyle n-k$ elements!

Hence there exists $\displaystyle 2^{n-k}$ of such B's in $\displaystyle \mathcal{P}(n)$.

Since we have $\displaystyle {n \choose k}$ elements in $\displaystyle \mathcal{P}(n)$ of length $\displaystyle k$, it follows we have $\displaystyle {n\choose k}2^{n-k}$ pairs $\displaystyle (A,B)\in \mathcal{P}(n)\times \mathcal{P}(n)$, where $\displaystyle A$ is a set of length $\displaystyle k$ and $\displaystyle A\subseteq B$.

Now we only need to sum over all different lengths $\displaystyle k$ a set $\displaystyle A$ can have. Thus we obtain:

Total amount of pairs $\displaystyle (A,B)$ = $\displaystyle \sum_{k=0}^{n}{n\choose k}2^{n-k}$.

And if we analyse this number close we can recognise the binomium of Newton again with $\displaystyle x= 1, y = 2$.

Hence we obtain: Total amount of pairs $\displaystyle (A,B) = 3^n$
Oh, thank you. You are a very good teacher.