# A combinatorial identity

$(*)\qquad\qquad\qquad\displaystyle\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk=4^n$.

One way to prove it is to count the number of possible triples $(A,B,C)$ of sets with $C\subseteq B\subseteq A\subseteq S=\{1,\dots,n\}$. This can be done in two ways. First, if $A, B, C$ contain $i,j,k$ elements respectively then the number of such triples clearly equals the left-hand side of $(*)$. On the other hand, since each element of $S$ must belong to one of the four disjoint regions in the picture below

the number of such triples equals precisely $4^n$.

An algebraic proof can be obtained by repeated use of the binomial theorem:

$\displaystyle 4^n=\sum_{n\ge i\ge 0}\binom ni3^i=\sum_{n\ge i\ge j\ge 0}\binom ni\binom ij2^j=\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk$.

Similarly, one obtains the more general identity

$\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\binom{n}{i_1}\binom{i_1}{i_2}\cdots\binom{i_{m-1}}{i_m}=(m+1)^n$.

This also follows from the multinomial theorem since the left-hand side equals

$\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\frac{n!}{(n-i_1)!(i_1-i_2)!\cdots (i_{m-1}-i_m)!i_m!}=(m+1)^n$.