¿Cómo demostrar$\sum_{k=1}^n \frac{2^k}{k}< 3\frac{2^n}{n}$?

Question

¿Cómo probar $$\sum_{k=1}^n \frac{2^k}{k}< 3\frac{2^n}{n}$$ and further $$\lim_{n\rightarrow \infty}\frac{n}{2^n}\sum_{k=1}^n \frac{2^{k}}{k} = 2$ $?

Estos resultados están verificados por la computadora, pero no puedo averiguar una prueba limpia.

Answer 1

Voy a responder a la segunda parte de la pregunta. Es útil notar que la suma

$$ S_n = \sum_{k=1}^n \frac{2^k}{k} $$

está dominado por sólo unos pocos términos cerca de $k=n$. En un sentido, los términos cerca del final constituye la principal contribución a la suma total, mientras que los términos cerca del principio son insignificantes. Podemos, por tanto, la esperanza de una buena estimación para el conjunto de la suma por la división de ella, aparte de que en estas dos piezas y la estimación de ellos de forma individual.

En este caso resulta que podemos dividir la suma de manera uniforme.

La primera mitad de la que puede salir con la estimación aproximada

$$ \begin{align} \sum_{k=1}^{\lfloor n/2 \rfloor} \frac{2^k}{k} &< \sum_{k=1}^{\lfloor n/2 \rfloor} 2^k \\ &= 2\left(2^{\lfloor n/2 \rfloor}-1\right) \\ &< 2^{n/2+1} \\ &= O\left(2^{n/2}\right). \end{align} \etiqueta{1} $$

Para ayudarnos a estimar la segunda mitad de la suma presentamos la nueva variable $h=n-k$. Tenga en cuenta que cuando se $\lfloor n/2 \rfloor + 1 \leq k \leq n$ tenemos $0 \leq h < n/2$.

El poder de la serie para $1/(1-x)$ converge uniformemente y absolutamente en el intervalo de $[0,1/2]$, así que podemos escribir $1/(1-x) = 1 + O(x)$ no. Entonces tenemos

$$ \begin{align} \frac{1}{k} &= \frac{1}{n-h} \\ &= \frac{1}{n} \cdot \frac{1}{1-h/n} \\ &= \frac{1}{n} \left[1 + O\left(\frac{h}{n}\right)\right] \\ &= \frac{1}{n} + O\left(\frac{h}{n^2}\right) \end{align} \etiqueta{$\star$} $$

para$n \geq 1$$\lfloor n/2 \rfloor + 1 \leq k \leq n$. Esto nos permite reescribir la segunda mitad de $S_n$

$$ \sum_{k=\lfloor n/2 \rfloor + 1}^{n} \frac{2^k}{k} = \frac{1}{n} \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k + \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k O\left(\frac{h}{n^2}\right). \etiqueta{2} $$

La primera suma en el lado derecho es

$$ \begin{align} \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k &= 2^{\lfloor n/2 \rfloor + 1} \sum_{k=0}^{\lceil n/2 \rceil - 1} 2^k \\ &= 2^{\lfloor n/2 \rfloor + 1} \left(2^{\lceil n/2 \rceil}-1\right) \\ &= 2^{n+1} + O\left(2^{n/2}\right), \end{align} $$

donde hemos utilizado el hecho de que $\lfloor n/2 \rfloor + \lceil n/2 \rceil = n$. Para la estimación de la segunda suma tenemos primero que volver a escribir en términos de $h$ $n$ sólo:

$$ \begin{align} \frac{1}{n^2} \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k h &= \frac{2^n}{n^2} \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^{k-n} h \\ &= \frac{2^n}{n^2} \sum_{h=0}^{\lceil n/2 \rceil - 1} 2^{-h}h. \end{align} $$

La cantidad de $\sum_{h=0}^{\lceil n/2 \rceil - 1} 2^{-h}h$ es limitado, así que para la segunda suma obtenemos la estimación

$$ \sum_{k=\lfloor n/2 \rfloor + 1}^{n} 2^k O\left(\frac{h}{n^2}\right) = O\left(\frac{2^n}{n^2}\right). $$

La combinación de estos y absorbiendo el primer término de error en el segundo nos encontramos con que $(2)$ se convierte en

$$ \begin{align} \sum_{k=\lfloor n/2 \rfloor + 1}^{n} \frac{2^k}{k} &= \frac{2^{n+1}}{n} + O\left(\frac{2^{n/2}}{n}\right) + O\left(\frac{2^n}{n^2}\right) \\ &= \frac{2^{n+1}}{n} + O\left(\frac{2^n}{n^2}\right). \end{align} $$

Mediante el uso de la estimación en $(1)$ se obtiene una estimación de la suma total,

$$ \begin{align} S_n &= \sum_{k=1}^{\lfloor n/2 \rfloor} \frac{2^k}{k} + \sum_{k=\lfloor n/2 \rfloor + 1}^{n} \frac{2^k}{k} \\ &= O\left(2^{n/2}\right) + \frac{2^{n+1}}{n} + O\left(\frac{2^n}{n^2}\right) \\ &= \frac{2^{n+1}}{n} + O\left(\frac{2^n}{n^2}\right). \end{align} $$

Así

$$ \frac{n}{2^n} \sum_{k=1}^{n} \frac{2^k}{k} = 2 + O\left(\frac{1}{n}\right). $$

Si usted desea más términos en la aproximación que puede tomar más términos en la expansión de la serie $(\star)$. Por ejemplo, tomando

$$ \frac{1}{k} = \frac{1}{n} + \frac{h}{n^2} + O\left(\frac{h^2}{n^3}\right) $$

los rendimientos

$$ \frac{n}{2^n} \sum_{k=1}^{n} \frac{2^k}{k} = 2 + \frac{2}{n} + O\left(\frac{1}{n^2}\right). $$

Answer 2

Sugerencia: probar LHS $<\dfrac{2^n}{n}(2+\dfrac{6}{n})$ cuando $n\ge3$

Answer 3

La desigualdad de $\sum_{k=1}^n 2^k/k \lt 3\cdot2^n/n$ puede ser probada por la comprobación de que para $n=1$, $2$ y $3$ y, a continuación, utilizando la desigualdad

$${3\over n}\le{4\over n+1}\text{ for } n\ge3$$

en un paso inductivo:

$$\begin{align} \sum_{k=1}^{n+1}{2^k\over k} &= \sum_{k=1}^n{2^k\over k}+{2^{n+1}\over n+1}\cr &\lt 3{2^n\over n}+{2^{n+1}\over n+1}\cr &\le {4\over n+1}2^n +{2^{n+1}\over n+1}\cr &=2{2^{n+1}\over n+1}+{2^{n+1}\over n+1}\cr &=3{2^{n+1}\over n+1}\cr \end{align}$$

El límite de $(n/2^n)\sum_{k=1}^n(2^k/k)$ puede ser determinado por la escritura de la suma como

$$\sum_{k=1}^n{n\over k}{1\over2^{n-k}}=\sum_{m=0}^{n-1}{n\over n-m}{1\over2^m}=\sum_{m=0}^{n-1}\left(1+{m\over n-m}\right){1\over2^m}=\sum_{m=0}^{n-1}{1\over2^m}+\sum_{m=0}^{n-1}{m\over n-m}{1\over2^m}$$

Ahora, la primera suma terminamos con es

$$\sum_{m=0}^{n-1}{1\over2^m}=1+{1\over2}+{1\over4}+\cdots+{1\over2^{n-1}}=2-{1\over2^{n-1}}$$

que claramente tiene límite de $2$$n\rightarrow\infty$. Por lo que sigue siendo para mostrar que la segunda suma,

$$\sum_{m=0}^{n-1}{m\over n-m}{1\over2^m}={0\over1\cdot n}+{1\over2(n-1)}+{2\over4(n-2)}+{3\over8(n-3)}+\cdots+{n-1\over2^{n-1}\cdot1}$$

tiende a $0$ $n$ tiende a $\infty$. Esto puede hacerse utilizando la más cruda de las estimaciones, siempre hemos dividido la suma en dos partes: los "principios" que $m/(n-m)$ es pequeña y la "tarde" piezas donde $1/2^m$ es pequeña. Un lugar conveniente para que la división en torno a $m=\sqrt[3]n$. Si lo hacemos, entonces los "principios" son los términos de todos menos de $\sqrt[3]n/(n-\sqrt[3]n)\approx n^{-2/3}$, de modo que la pieza es menor que $n^{-1/3}$, lo que tiende a $0$, mientras que el "atraso" que los términos están todos a menos de $n/2^{n^{1/3}}$, de modo que la pieza es menor que $n^2/2^{n^{1/3}}$, lo que también tiende a $0$. (Podría ser conveniente aquí para escribir $n=x^3$, por lo que estamos buscando en el límite de $x^6/2^x$$x\rightarrow\infty$. El punto es, la exponencial domina cualquier polinomio en el límite.)

Answer 4

Te respondo la segunda pregunta (que es más importante).

Escribirlo como $$\lim_{n\rightarrow\infty}\sum_{k=1}^n\frac{n}{k}\frac{1}{2^{n-k}}=2$$. We can split the sum at index $ a_n$. %#% $ De #% por otra parte, $$\sum_{k=1}^{a_n-1}\frac{n}{k}\frac{1}{2^{n-k}}\le\sum_{k=1}^{a_n-1}\frac{n}{1}\frac{1}{2^{n-k}}=n(\frac{1}{2^{n-a_n}}-\frac{1}{2^{n-1}})\le\frac{n}{2^{n-a_n}}$ $. Ahora es claro que sólo tenemos que elegir $$\sum_{k=a_n}^{n}\frac{n}{k}\frac{1}{2^{n-k}}\le\sum_{k=a_n}^{n}\frac{n}{a_n}\frac{1}{2^{n-k}}\le2\frac{n}{a_n}$ tal que $a_n$ $\displaystyle\frac{n}{a_n}\rightarrow 1$ mientras tanto es lo suficientemente grande como para eliminar el $2^{n-a_n}$. Tenemos un montón de opciones, por ejemplo, $n$.