Delimitación ${n \choose k}$

Question

Deje $k > 0$, e $n > 2k$. ¿Por qué es necesariamente cierto que $${n \choose k} > \frac{n^k}{2^k k!}$$ Y es la condición $n > 2k$ necesario para de esta desigualdad?

Answer 1

Si $k\le\frac12n$,$n-k+1>\frac12n$. Por lo tanto, $$ \begin{align} \binom{n}{k} &=\frac{n(n-1)(n-2)\dots(n-k+1)}{k!}\\ &>\frac{(n/2)^k}{k!}\\ &=\frac{n^k}{2^kk!}\tag{1} \end{align} $$ Sin embargo, la condición de que $k<\frac12n$ puede ser extendido a $k\le\frac34n$ señalando que para $0\le j\le k-1$, $(n-j)\color{red}{(n+j-k+1)}\ge n\color{red}{(n-k+1)}>n^2/4$. $$ \begin{align} \binom{n}{k}^2 &=\frac{n\color{red}{(n-k+1)}(n-1)\color{red}{(n-k+2)}(n-2)\dots(n-k+1)\color{red}{n}}{k!^2}\\ &>\frac{(n^2/4)^k}{k!^2}\tag{2} \end{align} $$ Tomando la raíz cuadrada de $(2)$ rendimientos $$ \binom{n}{k}>\frac{n^k}{2^kk!}\la etiqueta{3} $$ La Lleva Hasta El Límite:

Anteriormente, se muestra que la condición de $k<\frac12n$ en la pregunta puede ser extendido a $k\le\frac34n$. Uno podría preguntarse hasta qué punto este podría ser empujado. Es decir, ¿cuál es el mayor $\alpha$, de modo que $k<\alpha n$ implica $(3)$.

Multiplicando $(3)$ $k!$ y tomando el $\log$ de ambos lados de los rendimientos $$ \sum_{j=0}^{k-1}\log(n-j)>k\log(n)-k\log(2)\etiqueta{4} $$ Tomando nota de que $$ \sum_{j=0}^{k-1}\log(n-j)\ge\int_{n-k}^n\log(x)\,\mathrm{d}x\etiqueta{5} $$ Tenemos que $$ \int_{n-k}^n\log(x)\,\mathrm{d}x>k\log(n)-k\log(2)\etiqueta{7} $$ implica $(3)$. Calcular la integral en $(7)$ rendimientos $$ n\log(n)-n-(n-k)\log(n-k)+(n-k)>k\log(n)-k\log(2)\etiqueta{8} $$ Restando $k\log(n)-k$ desde ambos lados y dividiendo por $k$ rendimientos $$ \frac{n-k}{k}\log\left(\frac{n}{n-k}\right)>1-\log(2)\etiqueta{9} $$ Sustituyendo $\alpha=k/n$ rendimientos $$ \frac{1-\alpha}{\alpha}\log\left(\frac{1}{1-\alpha}\right)>1-\log(2)\etiqueta{10} $$ Aquí está una parcela de $\frac{1-\alpha}{\alpha}\log\left(\frac{1}{1-\alpha}\right)$$1-\log(2)$:

$\hspace{4cm}$

Podemos solucionar $\frac{1-\alpha}{\alpha}\log\left(\frac{1}{1-\alpha}\right)=\beta$ el uso de la función W de Lambert: $$ \begin{align} \frac{1-\alpha}{\alpha}\log\left(\frac{1}{1-\alpha}\right)&=\beta\tag{11}\\ (1-\alpha)^{1-\alpha}e^\beta&=e^{(1-\alpha)\beta}\tag{12}\\ (1-\alpha)e^{\beta/(1-\alpha)}&=e^\beta\tag{13}\\ -\beta/(1-\alpha)e^{-\beta/(1-\alpha)}&=-\beta e^{-\beta}\tag{14}\\ -\frac{\beta}{1-\alpha}&=W\left(-\beta e^{-\beta}\right)\tag{15}\\ \alpha&=1+\frac{\beta}{W\left(-\beta e^{-\beta}\right)}\tag{16} \end{align} $$ $(12)$: multiplicar por $-\alpha$, exponentiate, multiplicar por $e^\beta$

$(13)$: elevar a la $1/(1-\alpha)$ poder

$(14)$: tomar recíprocos, multiplicar por $-\beta$

$(15)$: aplicar $W$

$(16)$: resolver algebraicamente para $\alpha$

Conectar $\beta=1-\log(2)$ a $(16)$ da $$ \begin{align} \alpha &=1+\frac{1-\log(2)}{W\left(-\frac2e(1-\log(2))\right)}\\ &\approx 0.868708579475419252 \end{align} $$ Por lo tanto, si $k<\alpha n$, $(3)$ sostiene.

Ejemplo:

$\left.\binom{10000}{8687}\middle/\frac{1000^{8687}}{2^{8687}8687!}\right.=3.095040785$, pero $\left.\binom{10000}{8688}\middle/\frac{1000^{8688}}{2^{8688}8688!}\right.=0.8127577101$

Answer 2

Tenemos $$\binom{n}{k} = \frac{n!}{(n-k)!k!} \ge \frac{(n-k)^n}{(n-k)^{n-k}k!} \ge \frac{(n-k)^k}{k!} \ge \frac{(n/2)^k}{k!}$$ using $n > 2k \implica n-k \ge n/2$. In the more general case, as noted in the comments, you will need a more detailed analysis, e.g., using Stirling's approximation for $n!$.

Answer 3

Tenemos \begin{align*} \binom{n}{k} &> \frac{n^k}{2^k k!} \\ \frac{n!}{(n-k)!k!} &> \frac{n^k}{2^k k!} \\ \frac{n!}{(n-k)!} &> \frac{n^k}{2^k} \\ \prod_{i=n-k+1}^n i &> \left(\frac{n}{2}\right)^k \\ (n-k+1)^k &> \left(\frac{n}{2}\right)^k \\ n-k+1 &> \frac{n}{2} \\ n-2k+2 &> 0 \\ n+2 &> 2k \\ \end{align*}

Edit: $n > 2k$ no es una condición necesaria (por ejemplo, $n \geq 2k$ es buena), pero hay algo, en el caso general, la desigualdad no se sostiene, por ejemplo, para $n \geq 6$ tenemos $\binom{n}{n} = 1 \leq \frac{n^n}{2^n n!}$.