How can I calculate or at least approximate the sum? As a part of a complexity analysis of the algorithm, I have to calculate the following sum:
$$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}$$
Here $n$ is a fixed number.
After trying to derive the explicit formula, I gave up and tried to approximate it with the integral, which I was not able to calculate. Is there a way to get a formula or at least find the order of growth of this function when k-> $\infty $?
P.S. apart from the obvious thing that the sum is less than $k \cdot n$
 A: Proceeding naively,
$\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{array}
$
Since the series for
$e^{-x}$ is,
I believe,
enveloping,
the sum should be between
the partial sums of this.
However,
it looks to me that
the sums should be split into
two regions:
$2^i < \ln n$
and
$2^i \ge \ln n$
because the asymptotics
are different for these.
However,
it is late and 
I will leave it like this.
A: Using the inequality $e^{-x} \ge 1-x$, we have:
$\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$. 
Thus, $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$. 
So for fixed $n$ and large $k$, the sum is slightly less than $kn$.
A: $$
\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{align}
$$
Therefore,
$$
nk-n\log(n)\le\sum_{i=1}^kn^{(2^i-1)/2^i}\le nk
$$
A: Your sum is equivalent in $kn$.
Let $n \geq 1$ and $F(k) = \frac{1}{kn}(n^{1/2} + n^{3/4} + n^{7/8} + \dots + n^{1-1/2^k})$. As you point out, $0 \leq F(k) \leq 1$. Let $l = \liminf_{k \to +\infty} F(k)$. 
Now let $j$ be a fixed index. Leaving out the first $j$ terms, we have
$$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}}.$$
This shows that $l \geq n^{-1/2^{j+1}}$. But since $j$ was arbitrary, this implies that $l \geq 1$. Therefore $F(k) \to 1$.
