1
$\begingroup$

Bonjour,

The problem i have follows from the definition of the binomial coefficient:

$\frac{n(n-1)...(n-k+1)}{k!} = {n \choose k}$

For 0$\leq{i}$ and i less than k, we observe that:

$\frac{n-i}{k-i}\geq\frac{n}{k}$

Is there a simple and intuitive arithmetic proof of this inequality ?

This inequality is sometimes used to prove that:

$(\frac{n}{k})^k\leq {n \choose k}$

  • 0
    You also need $k\leq n$.2012-11-30

2 Answers 2

1

This is pretty straight forward. Note that $\frac{n-i}{k-i}\geq \frac{n}{k}$ iff $nk-ik\geq nk-ni$, which is true iff $-ik\geq -in$ which again is true (for our $i$) iff $k\leq n$, and this gives the answer.

  • 0
    user45150: thank you very much !2012-11-30
1

If $0 < i < k < n$, then $\frac{n-i}{k-i} = \frac{n}{k}\times\frac{1 - \frac{i}{n}}{1-\frac{i}{k}} > \frac{n}{k}$ since $1-\frac{i}{n} < 1 - \frac{i}{k}$. For an intuitive explanation let us look at a set of $n$ balls of which $k$ balls are blue and $n-k$ are not blue. Then, the proportion of blue balls in the set is $\frac{k}{n}$. Throw away $i$ blue balls. Then, the proportion of blue balls in the reduced set is smaller because you have thrown away proportionately far more blue balls than non-blue balls. That is, $\frac{k-i}{n-i} < \frac{k}{n} \Rightarrow \frac{n}{k} < \frac{n-i}{k-i}.$

  • 0
    I'll take a close look to this !2012-11-30