How do I start with $(k+1)^{x}(k+1)^{y}$ and arrive at $(k+1)^{x+y}$ using the BT?

Question

It's obvious that \begin{align} (k+1)^{x}(k+1)^{y}&=(k+1)^{x+y}. \end{align} But I'm stuck while deducing this with the BT after \begin{align} (k+1)^{x}(k+1)^{y}&=(\sum_{i=0}^{x}\binom{x}{i}k^{x-i})(\sum_{j=0}^{y}\binom{y}{j}k^{y-j})\\ &\overset{?}{=}\sum_{i=0}^{x}\sum_{j=0}^{y}\binom{x}{i}\binom{y}{j}k^{x+y-i-j}. \end{align} (I'm not sure if the last step is right.) Somehow I want to end up at \begin{align} \sum_{l=0}^{x+y}\binom{x+y}{l}k^{x+y-l}=(k+1)^{x+y}. \end{align} However, I don't know how $\binom{x}{i}\binom{y}{j}$ could look like $\binom{x+y}{l}$.

This is just something I'm looking into for the fun of it, I've already written the proof by induction that $x^{m}x^{n}=x^{m+n}$ for $m,n\in\mathbb{N}$ that my professor asked of us.

Answer 1

Here we transform the expression until we can finally apply the Vandermonde identity.

We obtain \begin{align*} \sum_{i=0}^x\binom{x}{i}k^{x-i}\sum_{j=0}^y\binom{y}{j}k^{y-j} &=\sum_{i=0}^x\binom{x}{i}k^{i}\sum_{j=0}^y\binom{y}{j}k^{j}\tag{1}\\ &=\sum_{i=0}^x\sum_{j=0}^y\binom{x}{i}\binom{y}{j}k^{i+j}\tag{2}\\ &=\sum_{l=0}^{x+y}\left(\sum_{{i+j=l}\atop{i,j\geq 0}}\binom{x}{i}\binom{y}{j}\right)k^{l}\tag{3}\\ &=\sum_{l=0}^{x+y}\left(\sum_{i=0}^l\binom{x}{i}\binom{y}{l-i}\right)k^{l}\tag{4}\\ &=\sum_{l=0}^{x+y}\binom{x+y}{l}k^{l}\tag{5}\\ \end{align*}

Comment:

• In (1) we exchange the order of summation in both sums by letting $i\rightarrow x-i$ and $j\rightarrow y-j$. Note that $\binom{x}{i}=\binom{x}{x-i}$ and $\binom{y}{j}=\binom{y}{y-j}$.

• In (2) we do some rearrangements by applying the distributive, associative and commutative law of real numbers.

• In (3) we introduce a new index variable $l:= i+j$ and exchange the order of summation from $$i\geq 0;j\geq 0\qquad\rightarrow\qquad l\geq 0; i+j=l; i\geq 0; j\geq 0$$

  If we consider two dimensional lattices, than the first indexing represents summation of columns row per row, while the second index range covers the same region by summing up along minor diagonals.

  We might also observe that since $0\leq l\leq x+y$, the upper limit is now $x+y$. So, the index $i$ in the inner sum might be greater than $x$ as well as the index $j$ in the inner sum might be greater than $y$. But this does not matter, since we use the rule \begin{align*} \binom{p}{q}=0\qquad\qquad q>p \end{align*}

• In (4) we use $j=l-i$ and get rid of $j$.

• In (5) we apply the Vandermonde identity.