How can I calculate or at least approximate the sum?

Question

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$

Answer 1

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.

Answer 2

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$.

Answer 3

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$.

Answer 4

$$ \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 $$