¿Cómo puedo calcular o aproximar al menos la suma?

Question

Como parte de un análisis de la complejidad del algoritmo, tengo que calcular la siguiente suma:

$$n^{1/2} + n^{3/4} + n^{7/8} + ...$$ where in total I have $k $ elements to sum: $% $ $\sum_{i=1}^{k}n^{(2^i-1)/2^i}$

Aquí $n$ es un número fijo.

Después de intentar derivar la fórmula explícita, me rindo y trató de aproximar con el integral, que no era capaz de calcular. ¿Hay una manera de obtener una fórmula o al menos encontrar el orden de crecimiento de esta función cuando k-> $\infty $?

P.D. aparte de lo obvio que la suma es menor que $k \cdot n$

Answer 1

Proceder ingenuamente,

$\begin{array}\\ \sum_{i=1}^{k}n^{(2^i-1)/2^i} &=\sum_{i=1}^{k}n^{1-1/2^i}\\ &=\sum_{i=1}^{k}nn^{-1/2^i}\\ &=n\sum_{i=1}^{k}e^{-\ln n/2^i}\\ &\approx n\sum_{i=1}^{k}(1-\ln n/2^i+(\ln n/2^i)^2/2)\\ &=n\sum_{i=1}^{k}1-n\ln n\sum_{i=1}^{k}1/2^i+\frac12 n\ln^2 n\sum_{i=1}^{k}1/4^i\\ &=nk-n\ln n(1-1/2^k)+\frac12 n\ln^2 n\frac{1/4-1/4^{k+1}}{1-1/4}\\ &\approx nk-n\ln n+\frac16 n\ln^2 n\\ \end{matriz} $

Puesto que la serie $e^{-x}$ es, creo, envolvente, la suma debe ser entre las sumas parciales de esta.

Sin embargo, me parece que las cantidades deben dividirse en dos regiones: $2^i < \ln n$ y $2^i \ge \ln n$ porque el multicelular es diferentes para éstos.

Sin embargo, es tarde y lo dejo como esta.

Answer 2

Usando la desigualdad $e^{-x} \ge 1-x$, tenemos:

$\displaystyle\sum_{i = 1}^{k}n^{-\tfrac{1}{2^i}}$ $= \displaystyle\sum_{i = 1}^{k}e^{-\tfrac{1}{2^i}\ln n}$ $\ge \displaystyle\sum_{i = 1}^{k}\left(1-\dfrac{1}{2^i}\ln n\right)$ $= k-\left(1-\dfrac{1}{2^k}\right)\ln n$.

Así, $kn-\left(1-\dfrac{1}{2^k}\right)n\ln n \le \displaystyle\sum_{i = 1}^{k}n^{1-\tfrac{1}{2^i}} \le kn$.

Para fijo $n$ % grande $k$, la suma es ligeramente menor que $kn$.

Answer 3

$$\begin{align} \sum_{i=1}^kn^{(2^i-1)/2^i} &=n\sum_{i=1}^kn^{-1/2^i}\\ &=n\sum_{i=1}^ke^{-\log(n)/2^i}\\ &\ge n\sum_{i=1}^k\left(1-\frac{\log(n)}{2^i}\right)\\[6pt] &\ge nk-n\log(n) \end {Alinee el} por tanto $$, $$ nk-n\log (n) \le\sum_ {i = 1} ^ kn ^ {(2^i-1)/2 ^ i} \le nk $$

Answer 4

Su suma es equivalente en $kn$.

Que $n \geq 1$ y $F(k) = \frac{1}{kn}(n^{1/2} + n^{3/4} + n^{7/8} + \dots + n^{1-1/2^k})$. Tal como usted señala, $0 \leq F(k) \leq 1$. Que $l = \liminf_{k \to +\infty} F(k)$.

Ahora que $j$ ser un índice fijo. Dejando de lado los primeros términos de la $j$, tenemos $$F(k) \geq \frac{1}{kn}(n^{1-1/2^{j+1}} + \dots n^{1-1/2^k}) \geq \frac{1}{k}(k-j)n^{-1/2^{j+1}} \xrightarrow[k \to +\infty]{} n^{-1/2^{j+1}}.$ $

Esto muestra que el $l \geq n^{-1/2^{j+1}}$. Pero puesto que $j$ era arbitrario, esto implica que el $l \geq 1$. Por lo tanto $F(k) \to 1$.