PERMUTATIONS Olympiad Number Theory Question

Question

AIMO 2020 Olympiad Permutation Questionenter image description here

This question was encountered during a mathematics competition, and I thought that Induction on k would be a suitable method of solving it. Am I right?

Answer 1

$$ \frac{m!}{m^k(m-k)!}=\frac{m(m-1)(m-2)\cdot\cdot\cdot(m-k+1)}{m^k}=\prod_{k=0}^{k-1}\big(1-\frac{k}{m}\big) $$ Similarly $$ \frac{n!}{n^k(n-k)!}=\prod_{k=0}^{k-1}\big(1-\frac{k}{n}\big) $$ Since $m<k$ it follows that for all $k$: $$ 1-\frac{k}{m}<1-\frac{k}{n} $$ and thus $$ \frac{m!}{m^k(m-k)!}<\frac{n!}{n^k(n-k)!} $$