Provide a combinatorial proof for an identity using the Binomial Theorem

Question

$$6^n= \sum_{0\leq j+k\leq n}^{n}\dbinom{n}{j}\dbinom{n-j}{k}2^j\cdot3^k.$$

To start, I tried expressing the LHS as a sum of terms: $$(2+3+1)^n = 6^n.$$ In this case, would I need to use the multinomial theorem instead? How should I proceed?

Answer 1

Just apply the binomial theorem twice: $$\begin{align*}6^n &= (2+4)^n \\ &= \sum_{j=0}^n \binom{n}{j}2^j 4^{n-j} \\ &= \sum_{j=0}^n \binom{n}{j}2^j (3+1)^{n-j} \\ &= \sum_{j=0}^n \binom{n}{j}2^j \sum_{k=0}^{n-j}\binom{n-j}{k}3^k \\ &= \sum_{j=0}^n\sum_{k=0}^{n-j} \binom{n}{j} \binom{n-j}{k}2^j 3^k\end{align*}$$

Answer 2

Yes, the multinomial theorem applies: \begin{align} 6^n &= (1+2+3)^n \\ &= \sum_{\substack{i,j,k\ge0:\\ i+j+k=n}} \binom{n}{i,j,k} 1^i 2^j 3^k \\ &= \sum_{\substack{i,j,k\ge0:\\ i+j+k=n}} \binom{n}{j}\binom{n-j}{k}\binom{n-j-k}{i} 1^i 2^j 3^k\\ &= \sum_{\substack{j,k\ge0:\\ j+k\le n}} \binom{n}{j}\binom{n-j}{k}2^j 3^k \end{align}

Your title requests a combinatorial proof. You could interpret this as the number of outcomes from rolling a six-sided die $n$ times. The LHS is clear. The RHS conditions on which $j$ rolls are in $\{2,3\}$ and which $k$ rolls are in $\{4,5,6\}$. (The remaining $n-j-k$ rolls are $1$.)

Answer 3

A combinatorial proof could be like the following. As you said $(2+3+1)^n=6^n$. We develop the RHS $$(2+3+1)\times(2+3+1)\times(2+3+1)\times\dots\times(2+3+1)$$ In the previous product, how many terms will be $2^j3^k1^l$, where $j+k+l=n$? First, we choose the $j$ parenthesis for the $2$ between the $n$ available, next we choose the $k$ for the $3$ between the $n-k$ left, finally the $1$ came from the remaining $l=n-j-k$ parenthesis. There are $${n\choose j}{n-j\choose k}{n-j-k\choose l}$$ ways of having $2^j3^k1^l$. Then $$6^n=(2+3+1)^n=\sum_{j+k+l=n}{n\choose j}2^j{n-j\choose k}3^k{n-j-k\choose l}1^l$$ $$6^n=(2+3+1)^n=\sum_{0\leq j+k\leq n}{n\choose j}{n-j\choose k}2^j3^k$$