# Inequality involving kth root of n choose k

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.

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

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.

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

$\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.

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

(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$.