# Binomial coefficients in Geometric summation

Guys please help me find the sum given below. $$\sum_{k=j}^i\binom{i}{k}\binom{k}{j}\cdot 2^{k-j}$$ (NOTE):The two coefficients are multiplied by 2 power (k-j)
I am using the formula: $\binom{r}{m}\binom{m}{q}=\binom{r}{q}\binom{r-q}{m-q}$
But not able to reach something fruitful.

If we set $N=i-j$, $$\begin{eqnarray*}\sum_{k=j}^{i}\binom{i}{k}\binom{k}{j}2^{k-j}=\frac{i!}{j!}\sum_{k=j}^{i}\frac{2^{k-j}}{(i-k)!(k-j)!}&=&\frac{i!}{j!}\sum_{k=0}^{N}\frac{2^k}{(N-k)!k!}\\&=&\frac{i!}{j!N!}\sum_{k=0}^{N}\binom{N}{k}2^k\\&=&\color{red}{\binom{i}{j}3^{i-j}}.\end{eqnarray*}$$

• Please explain your last move,rest awesome,thanks.. – Jaspreet Singh Jun 29 '15 at 22:05
• @JaspreetSingh : the last step is just the binomial theorem: $$\sum_{k=0}^{N}\binom{N}{k}x^k = (x+1)^k.$$ – Jack D'Aurizio Jun 29 '15 at 22:08

HINT: Start with a box of $i$ balls numbered from $1$ through $i$, so that they can be individually identified. There are $\binom{i}k$ ways to choose $k$ of them to move to a second box. There are then $\binom{k}j$ ways to choose $j$ of the balls in the second box to move to a third box. That leaves $k-j$ balls in the second box; there are $2^{k-j}$ ways to pick a subset of them to move to a fourth box. Thus, for each possible choice of $k$ there are

$$\binom{i}k\binom{k}j2^{k-j}$$

possible different outcomes. Clearly this is possible if and only if $j\le k\le i$. If you sum over all of these possible values of $k$, you count the ways to distribute $i$ white balls amongst four boxes in such a way that the third box has exactly $j$ balls in it.

• Can you find a closed expression in terms of $i$ and $j$ for the number of ways to distribute $i$ white balls amongst four boxes in such a way that the third box has exactly $j$ balls in it?
• can the other three boxes be empty in any of the case? – Jaspreet Singh Jun 29 '15 at 21:13
• @Jaspreet: Yes: in the first step $k$ might be $i$, in which case the first box ends up empty. And whatever $k$ is, after the $j$ balls are moved to the third box, we can move any subset of the balls remaining in the second box to the fourth, so the $k-j$ balls can end up distributed in any way between the second and fourth boxes. – Brian M. Scott Jun 29 '15 at 21:16
• considering what u said then answer would be $$\binom{i-j-1}{2}\$$ – Jaspreet Singh Jun 29 '15 at 21:17
• @Jaspreet: No, that binomial coefficient doesn’t really have anything to do with the problem. There are exactly $i-j$ balls in the other three boxes, and they can be distributed amongst those three boxes in any way at all. – Brian M. Scott Jun 29 '15 at 21:21

Suppose we are trying to evaluate $$\sum_{k=j}^n {n\choose k} {k\choose j} 2^{k-j}.$$

which is $$2^{-j} \sum_{k=j}^n {n\choose k} {k\choose j} 2^{k}.$$

Introduce $${k\choose j} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k}}{z^{j+1}} \; dz$$

which has the property that it is zero when $k\lt j,$ so we may extend $k$ back to zero to get $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} \sum_{k=0}^n {n\choose k} 2^k (1+z)^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} \left(1+2(1+z)\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} \left(2z+3\right)^n \; dz.$$

Extracting the coefficient we get $${n\choose j} 2^j 3^{n-j}$$ for a final answer of $${n\choose j} 3^{n-j}.$$

I hope you'll permit me to include this MSE link where the above method is used in a more sophisticated manner.

If you use the formula you noted you are changing two variable binomials by just one variable and the other is constant:

$$\sum_{k=j}^i\binom{i}{k}\binom{k}{j}\cdot 2^{k-j}=\sum_{j\le k\le i}\binom{i}{j}\binom{i-j}{k-j}2^{k-j}=\binom{i}{j}\sum_{0\le k-j\le i-j}\binom{i-j}{k-j}2^{k-j}$$

So you can see now a sum from zero to the upper parameter of the binomial coefficient multiplied by an exponent with the variable $k-j$, what is the definition of binomial expansion. Then

$$\sum_{j\le k \le i}\binom{i}{k}\binom{k}{j}\cdot 2^{k-j}=\binom{i}{j}(1+2)^{i-j}$$

These manipulations are valid for everything because $k$ and $j$ are entire numbers by definition of the binomial coefficient, and this is the unique condition where $\binom{i}{k}\binom{k}{j}=\binom{i}{j}\binom{i-j}{k-j}$ holds.

• Its there in Concrete Maths by Knuth – Jaspreet Singh Jun 29 '15 at 22:21

Well you were totally in right direction $\binom{i}{j}\cdot \sum_{k=j}^{k=i}$$\binom{i-j}{k-j}\cdot 2^{k-j} can be written as \binom{i}{j} \cdot \sum_{e=0}^{e=i-j}$$\binom{i-j}{e} \cdot 2^e$ .Apply binomial theorem to get the answer $\binom ij \cdot (1+2)^{i-j}$