This question arises from the following problem:
We define the set $N=\{1,2,...,n\}$. How many different possibilities are there to form three sets $A$, $B$ and $C$ such that $A\subseteq B\subseteq C\subseteq N$?
There are two ways to find the solution to this problem:
Strategy 1
For each $m\in N$, the element $m$ can be in the following sets:
- $m\notin A,B,C$.
- $m\notin A,B$ but $m\in C$.
- $m\notin A$ but $m\in B,C$.
- $i\in A,B,C$.
So, there are 4 possibilities for each element, and therefore the answer is $4^n$
Strategy 2
We know that the amount of different sets $C\in N$ with cardinal $i$ is ${n\choose i}$. Since we need $A\subseteq B\subseteq C\subseteq N$, the amount of possible ways to do it is:
$$w_n\equiv\sum_{k=0}^j\sum_{j=0}^i\sum_{i=0}^n{n\choose i}{i\choose j}{j\choose k}$$
I would like to prove that $w_n=4^n$. I tried to proceed by induction, proving that $w_n=4^n\Rightarrow w_{n+1}=4^{n+1}$. We know that, when we add the element $n+1$ to $N$, the only triplets $A$, $B$, $C$ that differ from the ones we could already form with $N=\{1,2,...,N\}$ are the ones where $n+1\in C$, and therefore we can separate:
$$w_{n+1}=\underset{=w_n}{\underbrace{\sum_{k=0}^j\sum_{j=0}^i\sum_{i=0}^n{n\choose i}{i\choose j}{j\choose k}}}+\underset{\equiv p_{n+1}}{\underbrace{\sum_{k=0}^j\sum_{j=0}^i\sum_{i=1}^{n+1}{n\choose i-1}{i\choose j}{j\choose k}}}$$
So, in order to prove that $w_{n=1}=n+1$, I would need to prove that $p_{n+1}=3\cdot 4^n$ by using the hypothesis $w_n=4^n$. This is where I am lost.
Any tips or advice to proceed, please? My intuition tells me I need to use properties such as ${m\choose n-1}+{m\choose n}={m+1\choose n}$, but I cannot get the desired result.
Your sum has a slight mistake. It should be $$w_n = \sum_{i=0}^n \sum_{j=0}^i\sum_{k=0}^j \binom{n}{i}\binom{i}{j}\binom{j}{k}$$ Can you see why?
Solving: $$\begin{align} w_n &= \sum_{i=0}^n \sum_{j=0}^i\sum_{k=0}^j \binom{n}{i}\binom{i}{j}\binom{j}{k} \\ &= \sum_{i=0}^n \sum_{j=0}^i \binom{n}{i}\binom{i}{j} \sum_{k=0}^j \binom{j}{k} \\ &= \sum_{i=0}^n\binom{n}{i}\sum_{j=0}^i\binom{i}{j}2^j \\ &= \sum_{i=0}^n\binom{n}{i}3^i \\ &= 4^n \tag*{$\blacksquare$} \end{align}$$