Mostrar que $\sum^k_{i=0} \binom{n}{i} \leq 2 \binom{n}{k}$, suma de ' la primera vez k ' coeficientes binómicos

Question

Estaba leyendo un artículo sobre teoría de la información y me encontré con este límite superior para la suma de la primera vez k coeficientes binómicos

Considerar el $n \in \mathbb{N}$.

$0 \leq k \leq \lceil\frac{n}{3}\rceil$ Tenemos

$\sum^k_{i=0} \binom{n}{i} \leq 2 \binom{n}{k}$

Encontré este artículo de mathoverflow sobre límites superior para la suma de la primera vez k Coeficientes binomiales, pero no he podido elaborar una prueba para él.

Answer 1

Sugerencia:$${n \choose i-1} = {n \choose i} \frac{i}{n+1-i} \le \frac{1}{2} {n \choose i} \ \text{if}\ i < \frac{n+1}{3}$ $

Answer 2

Como he indicados (hace siete años!) en ese post de MathOverflow, el cociente

$${\sum_{i=0}^k {n \choose i} \over {n \choose k}} = 1 + {k \over n-k+1} + {k(k-1) \over (n-k+1)(n-k+2)} + \cdots$$

se pueden limitar por encima por la serie geométrica

$$ 1 + {k \over n-k+1} + \left( k \over n-k+1 \right)^2 + \cdots = {n-(k-1) \over n-(2k-1)}. $$

Esto le da la desigualdad

$$ \sum_{i=0}^k {n \choose i} \le {n-(k-1) \over n-(2k-1)} {n \choose k}$$

y por lo que sólo necesitará demostrar que ${n-(k-1) \over n-(2k-1)} \le 2$ cuando $k \le \lceil n/3 \rceil$.

Answer 3

Fijar un número entero no negativo $k\leq \left\lceil\frac{n}{3}\right\rceil$. Para cada una de las $r=0,1,2,\ldots,k-1$, vamos a $S_r$ denota el conjunto de todos los $k$-subconjuntos de a $\{1,2,\ldots,n\}$ de la forma $A\cup \{n,n-1,\ldots,n-k+r-1\}$ $A$ $r$- subconjunto de $\{1,2,\ldots,k\}$. Debido a la suposición de $k\leq \left\lceil\frac{n}{3}\right\rceil$, que puede verse fácilmente que el $S_r$'s son mutuamente disjuntas. Como $\displaystyle\bigcup_{r=0}^{k-1}\,S_r$ se compone de $k$-subconjuntos de a $\{1,2,\ldots,n\}$, llegamos a la conclusión de que $$\sum_{r=0}^{k-1}\,\binom{n}{r}=\sum_{r=0}^{k-1}\,\left|S_r\right|=\left|\bigcup_{r=0}^{k-1}\,S_r\right|\leq \binom{n}{k}\,.$$ Esto es equivalente a la desigualdad.

P. S.: parece ser el caso de que esta prueba funciona para todos los números enteros no negativos $k\leq \left\lfloor\frac{n-1}{2}\right\rfloor$. La desigualdad también es estricto porque en $\{n,n-1,\ldots,n-k+1\}$ $k$- subconjunto de $\{1,2,\ldots,n\}$ que no se encuentran en cualquier $S_r$.