Triple Sigma Problem

Question

I am trying to evaluate the following: $$\sum_{i=0}^n \binom{n}{i} \sum_{j=0}^i \binom{i}{j} \sum_{k=0}^j \binom{j}{k}$$

So far I have got that $\sum_{k=0}^j \binom{j}{k} = 2^j$. I have played with $\sum_{j=0}^i \binom{i}{j} 2^j$ and after plugging in values I got that it is equal to $3^i$. I also discovered that $\sum_{i=0}^n \binom{n}{i} 3^i = 4^n$. How do I prove this, and evaluate the original sum?

Answer 1

By definition of the binomial expansion $$\sum_{k=0}^n\binom nka^kb^{n-k}=(a+b)^n$$ In particular $$\sum_{k=0}^n\binom nka^k=(a+1)^n$$ Now apply this identity thrice to get $4^n$ as you expect.

Answer 2

For a combinatorial proof, consider subsets $A\subseteq B \subseteq C \subseteq \{1,\dots,n\}$. The triple sum counts by constructing $C$, then $B$, then $A$. The expression $4^n$ counts according to whether each element is in $A$, $B\setminus A$, $C\setminus B$, or $\{1,\dots,n\}\setminus C$.