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.

  • $\begingroup$ My first thought would be to try and prove it by induction on $n$, have you tried that? $\endgroup$ Apr 14, 2020 at 18:41
  • $\begingroup$ OK, that may prove it but when I encountered the problem it had to be computed and NOT proved. I only modeled the question like this because I had programmed it and found that it was always equal to $5^n$ . $\endgroup$ Apr 14, 2020 at 18:45

3 Answers 3


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.


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.

  • $\begingroup$ And that's precisely what I was looking for! $\endgroup$ Apr 15, 2020 at 4:49

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


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


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.

  • 1
    $\begingroup$ Leaving a note here: the $1,2,3,4,5$ in your answer correspond to yellow, orange, red, blue and white balls in my answer respectively. $\endgroup$ Apr 14, 2020 at 18:53
  • $\begingroup$ Although your proof is probably the best method of doing this, but can it be done through a more rigorous, symbolic mathematics? $\endgroup$ Apr 14, 2020 at 19:18
  • $\begingroup$ @PriyanshRathi: What I did is rigorous. Do you mean some kind of algebraic argument? $\endgroup$ Apr 14, 2020 at 19:22
  • $\begingroup$ Sorry, my bad. Yes algebraic argument. $\endgroup$ Apr 14, 2020 at 19:26
  • $\begingroup$ @PriyanshRathi: I’m sure that there is, but I expect that it’s a bit messy and complicated, so I wasn’t interested in trying to come up with one. (Besides, I generally prefer combinatorial arguments, as I usually find them more intuitive.) $\endgroup$ Apr 14, 2020 at 19:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .