Prove that $\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$

Question

I have this math question that I'm kind of stuck on.

Prove that for all integers $1 < k \le n$, $$\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$$

I have to use mathematical induction on $k$ to prove this. So, I first check the base case $k=2$, I get $$f(2): \frac{\binom{n}{2}}{n^2} < \frac{\binom{n+1}{2}}{(n+1)^2}$$$$\frac{n(n-1)}{2n^2} < \frac{n(n+1)}{2(n+1)^2}$$$$= \frac{n-1}{n} < \frac{n}{n+1}$$

Now I assume that $f(z): \frac{\binom{n}{z}}{n^z} < \frac{\binom{n+1}{z}}{(n+1)^z}$ is true.

Check $f(z+1)$ is also true.

$$f(z+1): \frac{\binom{n}{z+1}}{n^{z+1}} < \frac{\binom{n+1}{z+1}}{(n+1)^{z+1}}$$ $$= \frac{\frac{n!}{(z+1)!(n-z-1)!}}{n^{z+1}} < \frac{\frac{(n+1)!}{(z+1)!(n-z)!}}{(n+1)^{z+1}}$$$$= \frac{n!}{n^{z+1}(z+1)!(n-z-1)!} < \frac{(n+1)!}{(n+1)^{z+1}(z+1)!(n-z)!}$$

I'm not sure what to do from here. Thanks.

Answer 1

Assume your calculation is correct up to the step

$\frac{n!}{n^{z+1}(z+1)!(n-z-1)!} < \frac{(n+1)!}{(n+1)^{z+1}(z+1)!(n-z)!}$

We can cancel the factor $(z+1)!$ in both denominators. Rewriting $(n+1)! = n! (n+1)$ and $(n-z)! = (n-z-1)!(n-z)$, we can simplify further to

$\frac{1}{n^{z+1}} < \frac{(n+1)}{(n+1)^{z+1} (n-z)}$

$\frac{1}{n} \cdot \frac{1}{n^z} < \frac{1}{(n+1)^z}\cdot \frac{1}{n-z}$

This is equivalent to showing that

$\frac{n-z}{n} \cdot \frac{(n+1)^z}{n^z} < 1.$

I do this by simplifying the LHS even further.

$\Big(1 - \frac{z}{n}\Big) \Big(1 + \frac{1}{n} \Big)^z$ (*)

At this step, I use Bernoulli's inequality to estimate

$1 - \frac{z}{n} \leq (1 - \frac{1}{n})^z$.

See here: https://en.wikipedia.org/wiki/Bernoulli%27s_inequality

Finally:

(*) $\leq \Big(1- \frac{1}{n}\Big)^z\Big(1 + \frac{1}{n}\Big)^z$

$= \Big[ \Big(1-\frac{1}{n}\Big) \Big(1+\frac{1}{n}\Big)\Big]^z = \Big(1-\frac{1}{n^2}\Big)^z < 1,$

which is the desired inequality.

Answer 2

First, I would just take a look at their ratio.

$\begin{array}\\ \frac{\frac{\binom{n+1}{k}}{(n+1)^k}} {\frac{\binom{n}{k}}{n^k}} &=\frac{\frac{\frac{(n+1)!}{k!(n+1-k)!}}{(n+1)^k}} {\frac{\frac{n!}{k!(n-k)!}}{n^k}}\\ &=\frac{\frac{(n+1)}{(n+1-k)}}{(1+1/n)^k}\\ &=\frac{\frac{(1+1/n)}{1+(1-k)/n}}{(1+1/n)^k}\\ &=\frac{1}{(1-(k-1)/n)(1+1/n)^{k-1}}\\ \end{array} $

For $a > 2$, $(1+1/n)^a >1+a/n+a(a-1)/(2n^2) $, so

$\begin{array}\\ (1-a/n)(1+1/n)^a &>(1-a/n)(1+a/n+a(a-1)/(2n^2))\\ &=(1+a/n+a(a-1)/(2n^2))-(a/n)(1+a/n+a(a-1)/(2n^2))\\ &=(1+a/n+a(a-1)/(2n^2))-(a/n)-(a^2/n^2)-a^2(a-1)/(2n^3))\\ &=1+((a(a-1)/2)-a^2)/(n^2))-a^2(a-1)/(2n^3))\\ &=1-(a(a+1)/2)/(n^2))-a^2(a-1)/(2n^3))\\ \end{array} $

so it looks like the denominator is less than $1$. To show this, let $f(x) =(1-ax)(1+x)^a $. Then $f(0) = 1$ and

$\begin{array}\\ f'(x) &=(1-ax)a(1+x)^{a-1}-a(1+x)^a\\ &=(1+x)^{a-1}(a(1-ax)-a(1+x))\\ &=(1+x)^{a-1}(a-a^2x-a-ax)\\ &=(1+x)^{a-1}(-a^2x-ax)\\ &=-ax(1+x)^{a-1}(a+1)\\ &<0 \end{array} $

Therefore $(1-(k-1)/n)(1+1/n)^{k-1} < 1 $ so $\frac{1}{(1-(k-1)/n)(1+1/n)^{k-1}} > 1 $ and the terms increase.