límite inferior de $\sum_{i=0}^{k}\binom{n}{i}$ para $k<n$

Question

Dados dos números positivos $n,k$ s.t. $k<n$ un límite superior para $\sum\limits_{i=0}^{k}\binom{n}{i}$ es $\frac{2n^k}{k!}$ . ¿Se conocen también límites inferiores? (en particular cuando $k=2^x-1$ y $n=x2^{x-1}$ para un número entero positivo $x$ ).

Answer 1

Tenga en cuenta que $\binom{n}{k} \geq \left(\frac{n}{k}\right)^k$ para $k > 0$ .

Entonces, $$\sum_{i = 0}^k \binom{n}{i} \geq 1 + \sum_{i=1}^k \left(\frac{n}{i}\right)^i \geq \sum_{i=0}^k \left(\frac{n}{k}\right)^i = \frac{\left(\frac{n}{k}\right)^{k+1} - 1}{\frac{n}{k} - 1}$$

Answer 2

La suma es el volumen de una esfera de Hamming en el $n$ hipercubo dimensional. Junto con la aproximación de Stirling, esto producirá esencialmente el límite inferior $2^{n H((k+1)/n)}$ donde $H(p)$ es la entropía binaria de Shannon y para su elección de $n,k$ probablemente será bastante bueno.