Out of a textbook.
Informally, the goal is to show that if from a given set of values ($2^n$ many values) in the range of $[0,m]$ (for fixed $m,k$), more than half are less than $m\cdot (1-\frac{1}{2^{k-1}})$, the average cannot be $m\cdot (1-\frac{1}{2^k})$.
The proof proceeds as follows:
let $\ell$ be the number of values less than $m(1-2^{-k})$,
let $u = 2^n - \ell$ be the number of values greater or equal $m(1-2^{-k})$
then the expected average $E \leq \frac{1}{2^n}\cdot \ell \cdot[m\cdot(1-2^{-k+1})-1] + u\cdot m$
assuming $E = m\cdot(1-2^{-k})$ will yield
$m\cdot(1-2^{-k}) \leq \frac{1}{2^n}\cdot \ell \cdot[m\cdot(1-2^{-k+1})-1] + u\cdot m$
and thus
$2^n\cdot m\cdot(1-2^{-k}) \leq \ell \cdot[m\cdot(1-2^{-k+1})-1] + u\cdot m$
which, I quote, "can only be satisfied for $ u > \ell $ ".
End of proof.
That claim isn't quite as obvious to me as it apparently should be. Why does it hold?
The whole thing is a bit unnnecessarily complicated. Instead of introducing $k$, it would be more straightforward to say more generally that if more than half the values are less than $m(1-\rho)$ and none of the values are greater than $m$, then the average can't be $m\left(1-\frac\rho2\right)$. This perhaps becomes more obvious if you consider transforming the values according to $x\to \frac{m-x}m$: if more than half the values are greater than $\rho$ and none are negative, the average can't be $\frac\rho2$.
Applying these transformations to your proof as a whole will probably also make it easier to check the claim you quoted.