# Greater than zero?

I need to show that

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

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?

-

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.

-
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
show 7 more comments