<s>[INST] Prove that $\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$ 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.
 [/INST] 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.
</s>