Una cota superior para $\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i}$?

Question

¿Alguien sabe de un razonable límite superior de los siguientes: $$\sum_{i = 1}^m \frac{\binom{i}{k}}{2^i},$$ donde le $k$ $m$ son fijos enteros positivos, y suponemos que $\binom{i}{k} = 0$ siempre $k > i$.

Un trivial límite superior utiliza la identidad $\binom{i}{k} \le \binom{i}{\frac i2}$, y el hecho de que $\binom{i}{\frac{i}{2}} \le \frac{2^{i+1}}{\sqrt{i}}$, para dar un salto de $$2\sum_{i = 1}^m \frac{1}{\sqrt{i}},$$ donde $\sum_{i = 1}^m \frac{1}{\sqrt{i}}$ es superior delimitada por $2\sqrt{m}$, lo que resulta en un límite de $4\sqrt{m}$. Podemos hacer mejor?

Gracias!

Yair

Answer 1

Sí, usted puede hacer mejor. De hecho $$ \sum_{i=k}^m \binom{i}{k} 2^{-i} \leq 2 $$ y esta obligado es agudo si $k$ es fijo e $m \to \infty$.

Para ver esto, considere la función $x^{k} (1 - x)^{-(k+1)}$ cerca de $0$; esto tiene un poder de expansión de la serie $$ \frac{x^k}{(1 - x)^{k+1}} = x^k \left( \sum_{\ell \geq 0} x^\ell \right)^{k+1} = \sum_{\ell \geq 0} \binom{k + \ell}{k} x^{\ell + k}, $$ (ver aquí) que, tras el cambio de la suma para empezar a $k$ en lugar de $0$, es igual a $$ \sum_{i \geq k} \binom{i}{k} x^i. $$ Ahora usted puede evaluar esta función en$x = \frac12$, lo que da $$ 2^{-k} 2^{k+1} = \sum_{i \geq k} \binom{i}{k} 2^{-i}. $$ Su serie es un truncamiento de esta suma, y así, ya que cada término es positivo, esto le da un límite superior. La nitidez proviene tomar el $m \to \infty$, por supuesto.

Puede mejorar esta obligado si usted sabe que $m$ no es mucho más grande de lo $k$. Aquí es una estimación, en el caso de $m = k + O(k/\log k)$. A continuación, $$ \sum_{i = k}^m \binom{i}{k} 2^{-i} \leq \sum_{i=k}^m i^{i-k} 2^{-i} = \sum_{i=k}^m e^{(i - k) \log i} 2^{-i} $$ Esta serie va a estar dominado por una serie geométrica $c^{-i}$ cualquier $1 < c < 2$ mientras que el exponente $(i - k) \log i = O(i)$, donde el implícita constante depende de $c$. Esto, a su vez satisfecho el requisito de $m - k = O(k/\log k)$, (o $k > m - O(\frac{m}{\log(m)}$). Específicamente, para cualquier $\varepsilon > 0$ tal que $e^\varepsilon < 2$ si $m \le k+ \frac{\varepsilon k}{\log(k)}$ o $k \ge m - \frac{\varepsilon m}{\log m}$, el argumento pasa a través de.

Por lo tanto, para cualquier $1 < c < 2$ hemos $$ \sum_{i = k}^m \binom{i}{k} 2^{-k} \leq \sum_{i=k}^m c^{-i} = O(c^{-k}) $$ si $m = k + O(k/\log k)$, donde el implícita constante depende de $c$.

Answer 2

Me gusta la Olla del argumento mejor, pero aquí es otro enfoque para aquellos que puedan estar interesados.

---

Puedo obtener una cota superior de a $2$, independiente de $k$$m$.

La aplicación de sumación por partes, tenemos, por $k \geq 2$, $$\begin{align*} \sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} &= \binom{m}{k} \sum_{i=1}^m \frac{1}{2^i} - \sum_{i=1}^{m-1} \left(\binom{i+1}{k} - \binom{i}{k}\right) \sum_{j=1}^i \frac{1}{2^j} \\ &= \binom{m}{k} \left(1 - \frac{1}{2^m}\right) - \sum_{i=1}^{m-1} \binom{i}{k-1} \left(1 - \frac{1}{2^i}\right)\\ &= \binom{m}{k} - \binom{m}{k}\frac{1}{2^m} - \sum_{i=1}^{m-1} \binom{i}{k-1} + \sum_{i=1}^{n-1} \binom{i}{k-1} \frac{1}{2^i}\\ &= \binom{m}{k} - \binom{m}{k}\frac{1}{2^m} - \binom{m}{k} + \sum_{i=1}^{m-1} \binom{i}{k-1} \frac{1}{2^i}\\ &= \sum_{i=1}^{m-1} \binom{i}{k-1} \frac{1}{2^i}- \binom{m}{k}\frac{1}{2^m}, \end{align*}$$ donde, en el segundo al último paso, usamos la parte superior de la sumación de identidad para los coeficientes binomiales, $\displaystyle \sum_{i=0}^m \binom{i}{k} = \binom{m+1}{k+1}$.

Dejando $\displaystyle F(m,k) = \sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i}$, esto significa que tenemos la recurrencia $$F(m,k) = F(m-1,k-1) - \binom{m}{k}\frac{1}{2^m},$$ valid for $k \geq 2$.

Desenrollar la recurrencia es fácil, y con $F(m-k+1,1) = 2 - \frac{m-k}{2^{m-k+1}} - \frac{3}{2^{m-k+1}},$ hemos

$$\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} = 2 - \frac{m-k}{2^{m-k+1}} - \frac{3}{2^{m-k+1}} - \sum_{i=0}^{k-2} \binom{m-i}{k-i} \frac{1}{2^{m-i}}.$$

Por lo tanto, $$\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} \leq 2.$$

Answer 3

Otra estimación para $\sum_{i=1}^m\frac1{\sqrt i}$ es $$2\sqrt{m-1}-2=\int_1^{m-1} x^{-1/2}\, dx \le \sum_{i=1}^m\frac1{\sqrt i}\le1+ \int_1^m x^{-1/2}\, dx=2\sqrt m-1. $$ Por lo tanto, podemos eliminar los sumandos con $i<k$ considerando $$ 4\sqrt m+2 -4\sqrt{k-2}$$

Answer 4

No responderle, pero algunos resultados sencillos que pueden ayudarte. Dejar $$S_{m,k} = \sum_{i=k}^m {i \choose k} 2^{-i}$$

entonces

$$ \sum_{k=0}^m S_{m,k} =m$$

$$ |S_{m,k+1} - S_{m,k} | \le \frac{m}{k}S_{m,k} $$