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?
 A: 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.
