Triple Summation of product of Binomial Coefficients $\sum_{k=0}^n\sum_{j=0}^n\sum_{i=0}^n\binom ni\binom{n-i}j\binom{n-j}k=5^n$?

Question

Prove that: $$\sum_{k=0}^n\sum_{j=0}^n\sum_{i=0}^n\binom ni\binom{n-i}j\binom{n-j}k=5^n$$

I have tried expanding the binomial coefficients as fractions of factorials. $\sum\sum\binom ni\binom{n-i}j$ gives the multinomial expansion of $3^n$ but I cannot handle the remaining term of $\binom{n-j}k$. I could not proceed further.

Btw I have checked the validity of the question by programming it.

Answer 1

Suppose you want to paint $n$ balls which are initially white, and you follow this procedure:

• You pick $i$ white balls and paint them yellow. ($\binom ni$ ways)
• You pick $j$ balls that are still white and paint them blue. ($\binom{n-i}j$ ways)
• You pick $k$ balls that aren't blue and paint them red. A ball that has been painted both red and yellow becomes an orange ball. ($\binom{n-j}k$ ways)

The number of ways to paint the balls like this forms the LHS. Alternatively, you could choose for each ball in turn whether to paint it red, yellow, blue or orange or leave it white – $5$ ways for each ball makes $5^n$ possibilities, the RHS. This is a combinatorial proof of the identity.

Answer 2

Here's a short direct proof via three applications of the binomial theorem: \begin{align} \sum_k \sum_j \sum_i \binom{n}{i} \binom{n-i}{j} \binom{n-j}{k} &=\sum_j \sum_i \binom{n}{i} \binom{n-i}{j} \sum_k \binom{n-j}{k} \\ &=\sum_j \sum_i \binom{n}{i} \binom{n-i}{j} 2^{n-j} \\ &=\sum_i \binom{n}{i} 2^i \sum_j \binom{n-i}{j} 2^{n-i-j} \\ &=\sum_i \binom{n}{i} 2^i 3^{n-i} \\ &=(2+3)^n \\ &=5^n \end{align} Note that this proof does not rely on knowing the resulting expression $5^n$ ahead of time.

Answer 3

I’m going to choose three subsets of $[n]$ as follows. First I choose any $i$ elements; call that set $A$. Then I choose $j$ of the remaining $n-i$ elements; call that set $B$. Finally, I choose $k$ of the $n-j$ elements in $[n]\setminus B$; call that set $C$. Now define a function $f_{A,B,C}:[n]\to[5]$ as follows:

$$f(k)=\begin{cases} 1,&\text{if }k\in A\setminus C\\ 2,&\text{if }k\in A\cap C\\ 3,&\text{if }k\in C\setminus A\\ 4,&\text{if }k\in B\\ 5,&\text{if }k\in[n]\setminus(A\cup B\cup C) \end{cases}$$

There are

$$\sum_{k=0}^n\sum_{j=0}^n\sum_{i=0}^n\binom{n}i\binom{n-i}j\binom{n-j}k$$

ways to choose the sets $A,B$, and $C$, and each such choice uniquely determines a function $f_{A,B,C}:[n]\to[5]$. It’s clear that each $f:[n]\to[5]$ is $f_{A,B,C}$ for some choice of $A,B$, and $C$, and there are $5^n$ such functions, so

$$\sum_{k=0}^n\sum_{j=0}^n\sum_{i=0}^n\binom{n}i\binom{n-i}j\binom{n-j}k=5^n\;.$$

Here’s a bit of intuition. The expression on the lefthand side clearly suggests that we should first choose $i$ elements of $[n]$, the set that I called $A$, and then a set $B$ of $j$ elements disjoint from $A$. The third set, $C$, of $k$ elements apparently should be disjoint from $B$ but not necessarily from $A$. This clearly divides $[n]$ into five parts: the integers that are only in $A$, the integers that are in both $A$ and $C$, the integers that are only in $C$, the integers that are in $B$, and the integers that weren’t chosen for any of the three sets. we can tag those five sets with five colors, as in Parcly Taxel’s answer, or with the five elements of $[5]$, or with any handy $5$-element set to get the result.