Prove that ${n \choose k} \ge (\frac{n}{k})^k$ for any given $n \ge k$ using induction

Question

I need to prove that ${n \choose k} \ge (\frac{n}{k})^k$ for any given $n \ge k$ using induction.
I started working on this but got stuck with the inductive step, namely I want to prove that
$${n \choose k} \ge \left(\frac{n}{k}\right)^k \Longrightarrow {n \choose k+1} \ge \left(\frac{n}{k+1}\right)^{k+1}$$
This is how I started:
$$\left( \frac{n}{k+1}\right)^{k+1} = \left(\frac{n}{k+1} \right) \left(\frac{n}{k+1}\right)^k \le \left(\frac{n}{k+1} \right) \left(\frac{n}{k} \right)^k \\ \le \underbrace{\left( \frac{n}{k+1}\right) {n \choose k}}_\text{hypothesis}$$ Right now, I don't see any reasonable way to continue with this. Any hints will be most appreciated. Thank you in advance for your answers.

Answer 1

First, observe that the inequality doesn't make sense if $k=0$, so we assume $1\leq k\leq n$ throughout.
The formula ${n\choose k}=\frac{n(n-1)\dots(n-k+1)}{k!}$ can be rewritten as $${n\choose k}=\prod_{i=0}^{k-1}\frac{n-i}{k-i}$$ so it suffices to see that for each $i$ we have $\frac{n-i}{k-i}\geq\frac{n}{k}$, which is immediate.
You can disguise this argument as an induction on $k$ (the statement being obvious for $k=1$ and any $n$) by rewriting the above formula as $${n\choose k}=\frac{n}{k}{n-1\choose k-1},$$ applying the induction hypothsesis to ${n-1\choose k-1}$, and noting as before that $\frac{n-1}{k-1}\geq\frac{n}{k}$.

Answer 2

HINT

I think you should apply the induction on $n$, notably

• Base case $k=n\implies {k \choose k} \ge \left(\frac{k}{k}\right)^k$
• Induction step assuming true ${n \choose k} \ge \left(\frac{n}{k}\right)^k$ prove that ${n+1 \choose k} \ge \left(\frac{n+1}{k}\right)^k$

Answer 3

Following @gimusi hint,

$\binom{n+1}{k} = \frac{n+1}{n+1-k} \binom{n}{k} \ge \frac{n+1}{n+1-k} \left(\frac{n}{k}\right)^k = \left(\frac{n+1}{k}\right)^k \left(\frac{n}{n+1}\right)^k \frac{n+1}{n+1-k} = \left(\frac{n+1}{k}\right)^k \frac{1}{\left(1+\frac{1}{n}\right)^k} \frac{1}{\left(1 - \frac{k}{n+1}\right)}$

So if we can show that $\frac{1}{\left(1+\frac{1}{n}\right)^k} \frac{1}{\left(1 - \frac{k}{n+1}\right)} \ge 1$, then we are done.

To prove:$\left(1+\frac{1}{n}\right)^k \left(1 - \frac{k}{n+1}\right) \le 1$

Even to a first degree, the above $= \left(1 + \frac{k}{n}\right) \left(1 - \frac{k}{n+1}\right) = 1 + \frac{k}{n(n+1)} - \frac{k^2}{n(n+1)}$

The case for $k = n+1$ is trivially correct. Assume $k = n$. So even then

$1 + \frac{n}{n(n+1)} - \frac{n^2}{n(n+1)} = 1 + \frac{1}{n+1}- \frac{n}{n+1} = \frac{2}{n+1}$ and we know $0 < \frac{2}{n+1} \lt 1$