I am given the following proof: \begin{align} &\sum^T_{i=k} \alpha^i (1-\alpha)^{T-i} \binom{T}{i} \\ &=\sum^T_{i=k} \alpha^i \binom{T}{i} \sum^{T-i}_{j=0} (-\alpha)^j \binom{T-i}{j} \\ &=\alpha^k \sum^{T-k}_{i=0} \frac{T!i!}{(T-k)!(i+k)!} \sum^{T-k-i}_{j=0} \alpha^i (-\alpha)^j \frac{(T-k)!}{i!j!(T-k-i-j)!} \\ &\le \alpha^k \binom{T}{k} \sum^{T-k}_{i=0} \sum^{T-k-i}_{j=0} \alpha^i (-\alpha)^j \frac{(T-k)!}{i!j!(T-k-i-j)!} \\ &=\alpha^k \binom{T}{k} \end{align}
The first equality is true from binomial theorem.
The second equality is the definition of binomial coefficients.
The third equality is true from multinomial theorem.
The inequality is what I don't understand. It is true that $$\frac{T!i!}{(T-k)!(i+k)!} \le \binom{T}{k}$$ for all $i$. And I thought that was the end of the proof. But the proof also says :
...where the inequality is true for $\alpha \le \frac{1}{T}$ since $\sum^{T-k-i}_{j=0} (-\alpha)^j \frac{(T-k)!}{i!j!(T-k-i-j)!} \ge 0$ for such $\alpha$ ...
How can we prove that $\sum^{T-k-i}_{j=0} (-\alpha)^j \frac{(T-k)!}{i!j!(T-k-i-j)!}$ is greater than $0$ only when $\alpha \le \frac{1}{T}$?
EDIT:
\begin{align} &\sum^T_{i=k} \alpha^i (1-\alpha)^{T-i} \binom{T}{i} \\ &=\sum^T_{i=k} \alpha^i \binom{T}{i} \sum^{T-i}_{j=0} (-\alpha)^j \binom{T-i}{j} \\ &=\alpha^k \sum^{T-k}_{i=0} \frac{T!i!}{(T-k)!(i+k)!} \sum^{T-k-i}_{j=0} \alpha^i (-\alpha)^j \frac{(T-k)!}{i!j!(T-k-i-j)!} \\ &\le \alpha^k \sum^{T-k}_{i=0} \binom{T}{k} \sum^{T-k-i}_{j=0} \alpha^i (-\alpha)^j \frac{(T-k)!}{i!j!(T-k-i-j)!} \\ \end{align}
Shouldn't the last inequality be true without the extra condition on $\alpha$?
Let $$c_j = (-\alpha)^j\frac{(T-k)!}{i!j!(T-k-i-j)!},$$ so that the sum in questions is $\sum_{j=0}^{T-k-i}{c_j}.$ Then the terms alternate in sign, and the first one positive. Therefore, if we can show that the terms decrease in absolute value, it follows that the sum is nonnegative.
Now $$|c_{j+1}/c_j| = \alpha \frac{j!}{(j+1)!} \frac{(T-k-i-j)!}{(T-k-i-j-1)!} = \alpha \frac{T-k-i-j}{j+1} <\frac{T-k-i-j}{T(j+1)}<\frac{1}{j+1}\le1$$
EDIT: The application of this is as follows. We have $$ \frac{T!i!}{(T-k)!}(i+k)! < \binom{T}{k}.$$ To see this, write down the definition of the binomial coefficient and cancel like terms. We find that we have to prove that $$\frac{i!}{(i+k)!}\le \frac{1}{k!} \text{, or} \binom{i+k}{k} \ge 1,$$ which is trivial. But now, we have to check that the sense of the inequality is preserved when we multiply by the second factor, so yes, it definitely matters that the second factor is $\ge 0$.