Afficher l'inégalité tient (coefficient binomial)

Question

J'ai du mal à comprendre comment montrer que l'inégalité est valable $ 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$$

Tous les conseils sur la façon d'aborder cela seraient très utiles.

Answer 1

$\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)$

Donc, $ \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})$

De même $ \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})$

Comme $n \gt m, (1-\frac{i}{n}) \gt (1-\frac{i}{m})$.

Cela devrait conduire à la preuve.

Answer 2

Je vais juste écrire un bref aperçu de la preuve.

Il vous suffit de montrer que l'inégalité est valable $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 $$

Expérimenter avec $k=2,3$ par exemple, vous verrez que vous pouvez appliquer une fameuse inégalité impliquant deux types différents de moyennes.

Answer 3

Il y a une interprétation combinatoire potentiellement intéressante à votre question.

Le nombre de fonctions de $[k] = \{1,\dots,k\}$ à $[n]$ est $n^k$. Le nombre de fonctions injectives de$[k]$ à $[n]$ est $\binom{n}{k} k!$(choisissez d'abord la plage, puis la bijection vers la plage). Ainsi votre inégalité se réduit à ce qui suit: la probabilité qu'une fonction aléatoire de$[k]$ à $[m]$ est injective est inférieure à la probabilité d'une fonction aléatoire de $[k]$ à $[n]$ est injectif.

Cela a un sens intuitif, car plus le codomaine est grand, plus il est «facile» pour une fonction aléatoire d'être injective.