Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to show that


given $K\geq k^*$, $0<a<1$ and $K$, $k^*\in\mathbb{Z^+/1}$.

I did some computer simulation and saw that it seems correct but analytically how can I show it?

share|cite|improve this question
up vote 1 down vote accepted

Us $i\binom{K}{i} = K\binom{K-1}{i-1}$ to rewrite this expression as:

$$\sum_{i=k^*}^KK\binom{K-1}{i-1}a^{i-1}(1-a)^{K-i-1} - \sum_{i=k^*}^KK\binom{K}{i}a^{i}(1-a)^{K-i-1}$$

Divide by the positive value $\frac{K}{1-a}$ and you want to show:

$$\sum_{i=k^*}^K\binom{K-1}{i-1}a^{i-1}(1-a)^{K-i} > \sum_{i=k^*}^K\binom{K}{i}a^{i}(1-a)^{K-i}$$

Now, given a coin with probability $a$ of coming up heads, the left hand side is the probability that, when tossing $K-1$ such coins, you will get at least $k^*-1$ heads.

The right hand side is the probability, if you toss $K$ such coins, that you will get at least $k^*$ heads.

But the only way to get at least $k^*$ heads in $K$ tosses is to get at least $k^*-1$ heads in the first $K-1$ tosses, so the odds of getting $k^*$ heads in $K$ tosses cannot be more than the odds of getting $k^*-1$ heads in $K-1$ tosses.

You get strict inequality because if they were equal, that means that every time you got exactly $k^*-1$ heads in the first $K-1$ tosses, you'd get a heads on the next toss. That would only be true if $a=1$ or if it was impossible to get exactly $k^*-1$ heads (in which case $a=0$ or $a=1$.)

Note, this inequality still works if $k^*=1$.

For a more explicit proof, write $\binom{K}{i} = \binom{K-1}{i-1} + \binom{K-1}{i}$. So:

$$\sum_{i=k^*}^K \binom{K}{i} a^i(1-a)^{K-i} = \sum_{i=k^*}^K\binom{K-1}{i-1}a^i(1-a)^{K-i} + \sum_{i=k^*}^K\binom{K-1}{i}a^i(1-a)^{K-i}$$

In the second sum, the term is zero when $i=K$, and therefore we get that:

$$\sum_{i=k^*}^K\binom{K-1}{i}a^i(1-a)^{K-i} = \sum_{i=k^*}^{K-1}\binom{K-1}{i}a^i(1-a)^{K-i} < \sum_{i=k^*-1}^{K-1}\binom{K-1}{i}a^i(1-a)^{K-i}$$

Changing variables $j=i+1$, this is:

$$\sum_{j=k^*}^K\binom{K-1}{j-1}a^{j-1}(1-a)^{K-j+1} $$

So we know that:

$$\sum_{i=k^*}^K \binom{K}{i} a^i(1-a)^{K-i} < \sum_{i=k^*}^K\binom{K-1}{i-1}a^i(1-a)^{K-i} + \sum_{j=k^*}^K\binom{K-1}{j-1}a^{j-1}(1-a)^{K-j+1}$$

But $a^i(1-a)^{K-i} + a^{i-1}(1-a)^{K-i+1} = a^{i-1}a^{K-i}(a + 1-a) = a^{i-1}a^{K-i}$

So we get that:

$$\sum_{i=k^*}^K \binom{K}{i} a^i(1-a)^{K-i} < \sum_{i=k^*}^K\binom{K-1}{i-1} a^{i-1}(1-a)^{K-i}$$

Which is what was to be proven. Notice, the inequality comes because we added the $i=k^*-1$ term to the sum, so that term is necessarily the difference.

share|cite|improve this answer
can I write left hand side as X+right hand side such that X is positive and I dont need to think about tossing a coin? )) – Seyhmus Güngören May 1 '12 at 16:11
Well, the difference is the probability that you get exactly $k^*-1$ heads in the first $K-1$ tosses, times the probability that the next toss is not heads, which is $1-a$, so the difference is $\binom{K-1}{k^*-1}a^{k^*-1}(1-a)^{K-k^*+1}$. So you can probably prove it directly, but the probability argument makes it clear what is going on. – Thomas Andrews May 1 '12 at 16:15
Yes in terms of understanding it is helpful. I cannot see easily that the difference is as your wrote from the formulas. I am thinking... – Seyhmus Güngören May 1 '12 at 16:29
I should add, that formula is the difference after dividing by $\frac{K}{1-a}$. The original difference is thus $\frac{K}{1-a}$ times that, which is $$K\binom{K-1}{k^*-1}a^{k^*-1}(1-a)^{K-k^*}$$ – Thomas Andrews May 1 '12 at 16:33
At any case when I add this difference to the left side I am not able to get the right side with some algebra. – Seyhmus Güngören May 1 '12 at 16:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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