How does one show that $$\sum_{j=k}^n\binom{j-1}{k-1}q^{j-k}=\sum_{j=k}^n\binom{n}{j}p^{j-k}q^{n-j},$$ where $p+q=1$? I suppose one needs to substitute $p=1-q$ on the right side and then use the binomial theorem, but it gets messy and I cannot get it done.

  • $\begingroup$ Did you try induction on $n$ $\endgroup$ – Elaqqad Mar 15 '15 at 16:28
  • $\begingroup$ @nokiddn there is a p^k missing on the left side $\endgroup$ – Lozenges Mar 15 '15 at 16:33
  • $\begingroup$ @Lozenges: thanks, fixed. $\endgroup$ – nokiddn Mar 15 '15 at 16:39

$$ \begin{align} \sum_{j=k}^n\binom{n}{j}(1-q)^{j-k}q^{n-j} &=\sum_{j=k}^n\sum_{i=0}^{j-k}\binom{n}{j}\binom{j-k}{i}(-q)^{j-k-i}q^{n-j}\tag{1}\\ &=\sum_{j=k}^n\sum_{i=0}^{j-k}\binom{n}{j}\binom{j-k}{i}(-1)^{j-k-i}q^{n-k-i}\tag{2}\\ &=\sum_{j=k}^n\sum_{i=k}^j\binom{n}{j}\binom{j-k}{i-k}(-1)^{j-i}q^{n-i}\tag{3}\\ &=\sum_{j=k}^n\sum_{i=k}^j\binom{n}{j}\binom{j-k}{j-i}(-1)^{j-i}q^{n-i}\tag{4}\\ &=\sum_{i=k}^n\sum_{j=i}^n\binom{n}{n-j}\binom{k-i-1}{j-i}q^{n-i}\tag{5}\\ &=\sum_{i=k}^n\binom{n+k-i-1}{n-i}q^{n-i}\tag{6}\\ &=\sum_{i=k}^n\binom{i-1}{i-k}q^{i-k}\tag{7}\\ &=\sum_{i=k}^n\binom{i-1}{k-1}q^{i-k}\tag{8} \end{align} $$ Explanation:
$(1)$: expand $(1-q)^{j-k}$ using the Binomial Theorem
$(2)$: separate powers of $-1$ and $q$
$(3)$: substitute $i\mapsto i-k$
$(4)$: $\binom{j-k}{i-k}=\binom{j-k}{j-i}$
$(5)$: $\binom{n}{j}=\binom{n}{n-j}$ and $\binom{j-k}{j-i}(-1)^{j-i}=\binom{k-i-1}{j-i}$
$(6)$: Vandermonde's Identity
$(7)$: substitute $i\mapsto n+k-i$
$(8)$: $\binom{i-1}{i-k}=\binom{i-1}{k-1}$

  • $\begingroup$ A very nice answer, thank you. Binomial coefficients with negative integers are new to me. One last question: so Vandermonde's Identity also holds for negative integers? $\endgroup$ – nokiddn Mar 16 '15 at 9:07
  • $\begingroup$ Vandermonde is most usually proven by considering the binomial expansions of $(1+x)^n(1+x)^m$ and $(1+x)^{n+m}$ and comparing powers of $x$. These expansions are valid for $m\lt0$. $\endgroup$ – robjohn Mar 16 '15 at 9:28
  • $\begingroup$ This answer talks a bit about negative binomial coefficients, and this answer gives a proof of Vandermonde's Identity using the method I describe above. $\endgroup$ – robjohn Mar 16 '15 at 17:21

Let's rewrite your identity slightly:

$$ \sum_{j=k}^n \binom{j-1}{k-1} p^k q^{j-k} = \sum_{j=k}^n \binom{n}{j} p^j q^{n-j}. $$

Imagine $n$ coins are tossed, each coin coming up heads with probability $p$. The right-hand side is the probability that at least $k$ coins came up heads. Each summand on the left-hand side is the probability that the $k$th head was on the $j$th toss; if there were at least $k$ heads, then such a $j$ must exist and is unique.

  • $\begingroup$ Upvote (+1) for simplicity and elegance. $\endgroup$ – Marko Riedel Mar 17 '15 at 2:35
  • $\begingroup$ This form of the equality is what I was trying to prove in the first place. And I indeed came across it studying times of successes of Bernoulli r.v. Thanks for a short and nice proof. $\endgroup$ – nokiddn Mar 17 '15 at 10:53

It follows from summation by parts and the identity: $$ \sum_{n=k}^{N}\binom{n}{k}=\binom{N+1}{k+1}$$ that is straightforward to prove by induction.

  • 1
    $\begingroup$ Sorry, can't seem to follow. Could you elaborate more on that? $\endgroup$ – nokiddn Mar 16 '15 at 8:28

Using complex variables we have the following result.

Suppose we are trying to compare (LHS) $$\sum_{j=k}^n {j-1\choose k-1} q^{j-k}$$ and (RHS) $$\sum_{j=k}^n {n\choose j} (1-q)^{j-k} q^{n-j}.$$

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

This gives for the LHS $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \sum_{j=k}^n (1+z)^{j} q^j \; dz$$

Simplify to obtain for the LHS $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \frac{(1+z)^{n+1} q^{n+1} - (1+z)^k q^k}{(1+z)q-1} \; dz$$ or $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \frac{(1+z)^{n+1} q^{n+1} - (1+z)^k q^k}{q-1+zq} \; dz$$

There are two pieces call them $A_1$ and $A_2$ given by $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \frac{(1+z)^{n+1} q^{n+1}}{q-1+zq} \; dz$$ and $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \frac{(1+z)^k q^k}{q-1+zq} \; dz.$$

We evaluate these with the substitution $z=1/w$ to get for $A_1$ $$\frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+1/w) q^k /w^k} \frac{(1+1/w)^{n+1} q^{n+1}}{q-1+q/w} \; \frac{dw}{w^2} \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+1/w) q^k w^{n+1-k}} \frac{(1+w)^{n+1} q^{n+1}}{q-1+q/w} \; \frac{dw}{w^2} \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+w) q^k w^{n+1-k}} \frac{(1+w)^{n+1} q^{n+1}}{w(q-1)+q} \; dw \\ = q^{n+1-k} \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{w^{n+1-k}} \frac{(1+w)^{n}}{w(q-1)+q} \; dw \\ = q^{n-k} \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{w^{n+1-k}} \frac{(1+w)^{n}}{w(q-1)/q+1} \; dw.$$

There are two contributions here from the poles at $w=q/(1-q)$ and at $w=0.$ The first one can be extracted from $$\frac{q^{n-k+1}}{q-1} \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{w^{n+1-k}} \frac{(1+w)^{n}}{w+q/(q-1)} \; dw$$ to get $$\frac{q^{n-k+1}}{q-1} \frac{(1-q)^{n+1-k}}{q^{n+1-k}} \frac{1}{(1-q)^n} = -\frac{1}{(1-q)^k}.$$

The second contribution is $$q^{n-k} \sum_{m=0}^{n-k} {n\choose n-k-m} \frac{(1-q)^m}{q^m} = q^{n-k} \sum_{m=0}^{n-k} {n\choose m+k} \frac{(1-q)^m}{q^m} \\ = q^{n-k} \sum_{m=k}^{n} {n\choose m} \frac{(1-q)^{m-k}}{q^{m-k}} = \sum_{m=k}^{n} {n\choose m} (1-q)^{m-k} q^{n-m}.$$

We get for $A_2$ $$\frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+1/w) q^k /w^k} \frac{(1+1/w)^{k} q^{k}}{q-1+q/w} \; \frac{dw}{w^2} \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+w) q^k /w^k} \frac{(1+1/w)^{k} q^{k}}{w(q-1)+q} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+w) q^k} \frac{(1+w)^{k} q^{k}}{w(q-1)+q} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{(1+w)^{k-1}}{w(q-1)+q} \; dw \\ = \frac{1}{q-1} \frac{1}{2\pi i} \int_{|w|=R} \frac{(1+w)^{k-1}}{w+q/(q-1)} \; dw.$$

This has no pole at zero and a pole at $w=q/(1-q)$ which contributes $$\frac{1}{q-1} \frac{1}{(1-q)^{k-1}} = - \frac{1}{(1-q)^{k}}.$$

Subtracting the contribution from $A_2$ from the one for $A_1$ we finally obtain $$\sum_{m=k}^{n} {n\choose m} (1-q)^{m-k} q^{n-m} - \frac{1}{(1-q)^{k}} - \left(-\frac{1}{(1-q)^{k}}\right) \\ = \sum_{m=k}^{n} {n\choose m} (1-q)^{m-k} q^{n-m}$$ which is precisely the result we were trying to prove, QED.


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.