$n < m$ implies $\frac{n-j}{m-j} \leq \frac{n}{m}$ for all $j$ such that $0 \leq j \lt m$?

Question

In "Introduction to Algorithms" by CLRS, section 11.4 states:

$n < m$ implies that $\frac{n - j}{m - j} \leq \frac{n}{m}$ for all $j$ such that $0 \leq j \lt m$

This section of the text assumes $n,m,j$ are all non-negative integers, and that $n \lt m$.

I'm struggling to derive a proof of this statement.

Intuitively I can understand that $m-j$ in the denominator increases the size of a fractional part: $\frac{1}{m-j} \gt \frac{1}{m}$, and by removing $j$ of these "larger" portions I will have $\frac{n - j}{m - j} \leq \frac{n}{m}$.

But I'm having trouble deriving an equality to prove this intuition. Any help?

Answer 1

We need to prove that $$mn-jm\leq mn-nj$$ or $$j(n-m)\leq0,$$ which is true.

Answer 2

$$\frac{n }{m } -\frac{n - j}{m - j} = \frac{mn-jn-mn+jm}{m(m - j)}= \frac{j(m-n)}{m(m - j)} >0$$

Answer 3

Consider $f(x) = \frac{n-x}{m-x}$ on $[0,m)$. $f$ is differentiable there. We can write $$f(x)=\frac{m-x-(m-n)}{m-x}=1-\frac{m-n}{m-x}$$ so $$f'(x)=-\frac{m-n}{(m-x)^2} < 0$$ This means $f$ is strictly decreasing on $[0,m)$, so $$f(x)\leq f(0)=\frac nm$$