Checking $( \binom{n}{k} - \binom{n-k}{k}) / \binom{n}{k} < \frac{k^2}{n}$ Let $n$ and $k$ be integers with $2\leq k \leq n$. I want to check the inequality
$$\left( \binom{n}{k} - \binom{n-k}{k} \right) / \binom{n}{k} < \frac{k^2}{n}$$
which occurs in a paper I am currently reading. For fixed $k$ and $n\to \infty$ one should get asymptotic equality. There should be a "elementary" proof. Here is my question:
Why does this inequality hold?
Direct calculation didn't succeed so far. It might be useful to observe that the inequality is equivalent to
$$ 1- \binom{n-k}{k}/\binom{n}{k} < \frac{k^2}{n} .$$
The asymptotic equality will probably follow directly from the proof.
 A: Let $S$ be a set chosen uniformly at random from all size $k$ subsets of $[n]=\{1,2,\dots n\}$.   The probability that $S$ is also a subset of $\{1,2,\dots,n-k\}$ is $\frac{\binom{n-k}{k}}{\binom{n}{k}}$.  So the left side of your inequality corresponds to the probability that $S$ contains at least one number larger than $n-k$.  Call this event $A$.
We can think of $S$ as $\{x_1, x_2, \dots, x_k\}$, where the $x_i$ are $k$ elements successively drawn randomly without replacement from $[n]$.  Note that each $x_i$ is uniform on $[n]$ (this is clear for $x_1$, and by symmetry $x_j$ and $x_1$ have the same distribution for $j>1$) , but the $x_i$ are not independent due to the constraints that they are all unequal.
For $1 \leq j \leq k$, let $A_j$ be the event that $x_j$ is the first of the $x_i$ which is larger than $n-k$.  In other words, $A_j$ is the event that all of $x_1, x_2, \dots, x_{j-1}$ are at most $n-k$, but $x_{j}>n-k$.  This event is disjoint, and their union is $A$.  It follows that
$$P(A) = \sum_{j=1}^k P(A_j)$$
But $P(A_1)=\frac{k}{n}$, and for $j > 1$ we have
$$P(A_j) < P(x_j>n-k) = \frac{k}{n}$$
So this last sum is strictly less than $\frac{k^2}{n}$.
A: (Not quite as sharp as you asked for, but good enough for your purposes.)
For $ n < 2k$,  the LHS is 1 and the RHS is $ >1$, so done.
Henceforth, assume that $ n \geq 2k$ (so we don't divide by 0).
Show that  (Fill in the gaps. If you're stuck, explain what you've tried.)
1.
$$ \frac{ n \choose k } { n - k \choose k } = \frac{ (n-k)! (n-k)! } { n! (n-2k)! } = \prod_{i=0}^{k-1} \frac{ n-k-i } { n-i }.$$
2.
$$\prod_{i=0}^{k-1} \frac{ n-k-i } { n-i } = \prod ( 1 - \frac{k}{n-i}) \geq 1 - \sum_{i=0}^{k-1} \frac{k}{n-i} \geq  1 - \frac{k^2} { n-k+1}.$$
3.
$$\left( \binom{n}{k} - \binom{n-k}{k} \right) / \binom{n}{k} \leq \frac{k^2}{n-k + 1}$$
