2
$\begingroup$

I am trying to prove the following inequality:

$\sqrt[k]{n\choose k} \le n-k+1$.

I have not managed to find anything whatsoever on this, although I am very positive it is true.

Could there be a way to prove this involving ${n\choose k}\le(\frac{en}{k})^k$ by showing $(\frac{en}{k})^k\le (n-k+1)^k$ and taking the root?

For context: I am trying to show that for

$(1+\frac{\epsilon}{x})^n<(1+\epsilon)$, $x=\frac{n(n+1)}{2}$ would suffice.

$\endgroup$
  • $\begingroup$ I assume that you want to restrict $0 \le k \le n$, otherwise it would be wrong for large $k$. $\endgroup$ – Martin R Aug 21 '17 at 19:34
  • $\begingroup$ Correct, k should be $\le$ n $\endgroup$ – Moonbear Aug 22 '17 at 6:50
2
$\begingroup$

Suppose we have $n \geq k \geq i+1$ so $ k-i-1 \geq 0$ and multiply this by the first inequality. We have \begin{eqnarray*} k (k-i-1) & \leq & n (k-i-1) \\ n -i & \leq & nk -k^2 +k -in +ik -i = (n-k+1)(k-i) \\ \frac{n-i}{k-i} & \leq & n-k+1 \end{eqnarray*} Now multiply this inequality together for $i=0,1, \cdots k-1$ and we have \begin{eqnarray*} \binom{n}{k}=\frac{n}{k}\frac{n-1}{k-1} \cdots \frac{n-i}{k-i} \cdots \frac{n-k+1}{1} \leq (n\color{red}{-}k+1)^k. \end{eqnarray*} Now take the $k^{th}$ root and we have the result.

$\endgroup$
  • $\begingroup$ @MartinR ... oops ... Well spotted. Thanks. $\endgroup$ – Donald Splutterwit Aug 21 '17 at 19:40
  • $\begingroup$ My answer is an attempt to do this in a similar way. $\endgroup$ – marty cohen Aug 21 '17 at 20:51
1
$\begingroup$

$\sqrt[k]{n\choose k} \le n-k+1$ is equivalent to ${n\choose k} \le (n-k+1)^k $.

$\begin{array}\\ {n\choose k} &=\dfrac{n!}{k!(n-k)!}\\ &=\dfrac{\prod_{i=0}^{k-1}(n-i)}{ k!}\\ &=\dfrac{\prod_{i=0}^{k-1}(n-i)}{\prod_{i=1}^k i}\\ &=\dfrac{\prod_{i=0}^{k-1}(n-i)}{\prod_{i=0}^{k-1} (k-i)}\\ &=\prod_{i=0}^{k-1} \dfrac{n-i}{k-i}\\ \end{array} $

so if $\dfrac{n-i}{k-i} \le n-k+1 $ we are done.

This is the same as

$\begin{array}\\ n-i &\le (k-i)(n-k+1)\\ &=k(n-k+1)-i(n-k+1)\\ \end{array} $

or

$\begin{array}\\ i(n-k) &\le k(n-k+1)-n\\ &= k(n-k)+k-n\\ &= (k-1)(n-k)\\ \end{array} $

or $i \le k-1 $ which is true.

$\endgroup$
  • $\begingroup$ Your answer is essentially what I had written in my notebook ... I just reversed the order of the argument. $\endgroup$ – Donald Splutterwit Aug 21 '17 at 20:58
  • $\begingroup$ I wanted to see how easy it would be to derive it going forward. Of course I upvoted your answer. $\endgroup$ – marty cohen Aug 21 '17 at 21:04
1
$\begingroup$

(This is quite similar to and inspired by Donald Splutterwit's answer.)

Using $$ 1 < x \le y \quad \Longrightarrow \quad \frac{y}{x} \le \frac{y-1}{x-1} $$ it follows that for $1 \le k \le n$ $$ \frac{n}{k} \le \frac{n-1}{k-1} \le \frac{n-2}{k-2} \le \dots \le \frac{n-(k-1)}{k-(k-1)} = n-k+1 $$ and therefore $$ \binom{n}{k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \frac{n-2}{k-2} \cdots \frac{n-(k-1)}{k-(k-1)} \le (n-k+1)^k \, . $$ and this holds for $k=0$ as well.


Your idea to show that $$ {n\choose k}\le(\frac{en}{k})^k \le (n-k+1)^k $$ cannot work because the second inequality does not hold for $k = n$.

$\endgroup$

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.