Corto e intuitiva prueba de que $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$

Question

La simple desigualdad que $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$ tiene un número de diferentes pruebas. Pero hay una en particular intuitiva, a corto y elegante prueba que utiliza la interpretación natural de los coeficientes binomiales, por ejemplo. Yo ideal sería una prueba de que también es accesible a los estudiantes con escasos conocimientos previos.

Aquí es la mejor prueba de que he visto que es menos intuitivo de lo que yo estaba esperando.

Primero debemos demostrar primero que $$\frac{n-i}{k-i} \geq \frac{n}{k}$$ para $i<k\leq n$. Esto se deduce de la $$0\leq (n-k)i = k(n-i) - n-(k-i) = k(k-i)\left(\frac{n-i}{k-i}-\frac{n}{k}\right),$$ y $k(k-i)> 0$, lo $(n-i)/(k-i) \geq n/k.$

Ahora multiplicamos la más $i\in\{1,\ldots,k-1\}$ obtener $$\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1} \geq \frac{n^k}{k^k},$$ o, equivalentemente,$\binom{n}{k}\geq (n/k)^k$.

Answer 1

$n^k$ es el número de maneras de escoger a $k$ bolas de $n$ bolas con la repetición permitido. Uno puede generar todas las formas posibles por primera decidir cuál $k$ $n$ bolas para dibujar y sacar de la $k$ seleccionado las bolas en su lugar. Hay $\binom{n}{k}$ formas de elegir el $k$ bolas y $k^k$ maneras de escoger el $k$ bolas con la repetición permitido. Esto nos da $$n^k \le\binom{n}{k} k^k \quad\iff\quad \left(\frac{n}{k}\right)^k \le \binom{n}{k}$$

Answer 2

Nota primero que para todos los $0 \leq i < k \leq n$ tenemos $k(n-i) = kn - ki > kn - ni =\geq n(k-i)$, y, por tanto,$\frac{n-i}{k-i} \geq \frac{n}{k}$. Por lo tanto $${n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1} = \prod_{i=0}^{k-1} \frac{n-i}{k-i} \geq \prod_{i=0}^{k-1} \frac{n}{k} = \left(\frac{n}{k}\right)^k.$$

Answer 3

Para cada $1\leqslant k\leqslant n$$0\leqslant i\leqslant k-1$, $$ k\leqslant n\implica\frac{i}k\geqslant\frac{i}n\implica 1-\frac{i}k\leqslant1-\frac{i}n. $$ Cada término es positivo, de ahí que los productos están en el mismo orden, es decir, $$ \frac{k!}{k^k}=\prod_{i=0}^{k-1}\left(1-\frac{i}k\right)\leqslant\prod_{i=0}^{k-1}\left(1-\frac{i}n\right)=\frac{n!}{n^k(n-k)!}. $$ Multiplicar por la izquierda y de la derecha términos por $\dfrac{n^k}{k!}$... Et voilà!