<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] 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. 
</s>