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.
Thanks in advance.


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*}$$

  • $\begingroup$ Please explain your last move,rest awesome,thanks.. $\endgroup$ – Jaspreet Singh Jun 29 '15 at 22:05
  • $\begingroup$ @JaspreetSingh : the last step is just the binomial theorem: $$\sum_{k=0}^{N}\binom{N}{k}x^k = (x+1)^k.$$ $\endgroup$ – 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


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?
  • $\begingroup$ can the other three boxes be empty in any of the case? $\endgroup$ – Jaspreet Singh Jun 29 '15 at 21:13
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jun 29 '15 at 21:16
  • $\begingroup$ considering what u said then answer would be $$\binom{i-j-1}{2}\$$ $\endgroup$ – Jaspreet Singh Jun 29 '15 at 21:17
  • $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ Its there in Concrete Maths by Knuth $\endgroup$ – 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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.