I'm struggling to understand how to show that the inequality holds for $ m,n \in \mathbb{N} \; \text{with} \; m<n $ $$\frac{1}{m^k} {m \choose k} < \frac{1}{n^k} {n \choose k} \;\; \text{for all} \; k=2,...,m$$
Any pointers of how to approach this would be very helpful.
$\frac{1}{m^k} {m \choose k} < \frac{1}{n^k} {n \choose k} \;\; \text{for all} \; k=2,...,m$
$\displaystyle {m \choose k} = \frac{m!}{(m-k)!k!} = \frac{1}{k!}\prod_{i=0}^{k-1} (m-i)$
So, $ \displaystyle \frac{1}{m^k} {m \choose k} = \frac{1}{k!}\prod_{i=0}^{k-1} \frac{m-i}{m} = \frac{1}{k!}\prod_{i=0}^{k-1} (1-\frac{i}{m})$
Similarly $ \displaystyle \frac{1}{n^k} {n \choose k} = \frac{1}{k!}\prod_{i=0}^{k-1} \frac{n-i}{n} = \frac{1}{k!}\prod_{i=0}^{k-1} (1-\frac{i}{n})$
As $n \gt m, (1-\frac{i}{n}) \gt (1-\frac{i}{m})$.
This should lead to the proof.
I will just write a brief outline of the proof.
You only need to show the inequality holds for $n=m+1$.
$$ \frac{1}{m^k} {m \choose k} < \frac{1}{(m+1)^k} {n \choose k} \iff (m-k+1)(m+1)^k < (m+1) m^k $$
$$ \iff (m-k+1)(m+1)^{k-1} < m^k $$
Experiment with $k=2,3$ for example, you will see you can apply some famous inequality involving two different kind of averages.
There's a potentially interesting combinatorial interpretation to your question.
The number of functions from $[k] = \{1,\dots,k\}$ to $[n]$ is $n^k$. The number of injective functions from $[k]$ to $[n]$ is $\binom{n}{k} k!$ (first choose the range, then the bijection to the range). Thus your inequality reduces to the following: the probability a random function from $[k]$ to $[m]$ is injective is less than the probability a random function from $[k]$ to $[n]$ is injective.
This makes some intuitive sense, since the larger the codomain, the 'easier' it is for a random function to be injective.
