I have $3$ positive integers $i, k, q$, satisfying $1 \le k \le i \le q$. I am trying to prove the following inequality: $$\frac{{\left( {\begin{array}{*{20}{c}} {q - k}\\ {i - k} \end{array}} \right)}}{{\left( {\begin{array}{*{20}{c}} q\\ i \end{array}} \right)}} = \frac{{\left( {i - k + 1} \right) \cdot \left( {i - k + 2} \right) \cdot ... \cdot \left( i \right)}}{{\left( {q - k + 1} \right) \cdot \left( {q - k + 2} \right) \cdot ... \cdot \left( q \right)}} \le \frac{{{i^k}}}{{{q^k}}}$$

Note that ${\left( {i - k + 1} \right) \cdot \left( {i - k + 2} \right) \cdot ... \cdot \left( i \right) \le {i^k}}$ and ${\left( {q - k + 1} \right) \cdot \left( {q - k + 2} \right) \cdot ... \cdot \left( q \right) \le {q^k}}$, making the inequality non-trivial. I considered the following cases:

  1. $k=1$. The inequality becomes $1 \le 1$ which is of course true.
  2. $k=2$. The inequality becomes $i \le q$ which is true.
  3. $k=3$. The inequality becomes $\frac{{q + i}}{{qi}} \le \frac{3}{2}$ which seems true, but proof is needed.

For $k=4$ and on the expressions become complicated (unless they can be simplified somehow). Any help would be highly appreciated.


Hint. Show that $\frac{i-k+1}{q-k+1} \leq \frac i q$

  • $\begingroup$ Done. Now by showing that $\frac{{i - k + j}}{{q - k + j}} \le \frac{i}{q}$ for $j \le k$ the inequality follows. Thanks. $\endgroup$ – r1c Feb 25 '14 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.