Bounding a convergent sum Let $\lg = \log_2$ and $n$ be a positive integer. I am trying to find an upper bound on the growth rate of the following sum:
$$S_n=\sum_{i=1}^{n} \frac{1}{2^ii}e^{-n/2^i}$$
Clearly the sum converges, and furthermore it seems like $\lim_{n\to \infty}S_n = 0$. It seems like the terms achieve a maximum around $i\approx \lg(n)$ and most other terms are much smaller (i.e., don't contribute much to the sum). Given this, it seems like we have $$S_n \leq c\frac{1}{n\lg n}$$ for some $c>0$.
If we were to omit the factor of $i$ in the denominator, then the sum could be easily bounded by integrating $e^{-nx}$ over a suitable interval. Similarly, if we were to drop the factor of $e^{-n/2^i}$, then we could bound the sum by the closed form for $\sum\limits_{i=1}^\infty \frac{x^i}{i} \bigg|^{x=\frac{1}{2}}$. But with both of them together, I am not sure how to proceed.
 A: For each $n$, let $f_n(x) = \frac{\exp(-n/2^x)}{2^x x}$. Then we can show that(1),(2)
$$ \left| \sum_{i=1}^{n} f_n(i) - \int_{1}^{n} f_n(x) \, \mathrm{d}x \right| \leq \max_{1\leq x \leq n} f_n(x). $$
(This is essentially becaues $f_n$ is unimodal.) To estimate the maximum, we note that
\begin{align*}
f_n'(x) = 0
&\quad\iff\quad (\log f_n(x))' = 0 \\
&\quad\iff\quad \frac{n}{2^x} = 1+ \frac{1}{x \log 2} \\
&\quad\iff\quad \log n - x \log 2 = \log\left(1 + \frac{1}{x \log 2}\right).
\end{align*}
Inspecting the last equation, it is not hard to show that the equation has a unique zero $x_*$ in $[1, \infty)$. Moreover, for $n$ large enough,
\begin{align*}
x = \log_2(n/2) &\quad\implies\quad \frac{n}{2^x} = 2 > 1+ \frac{1}{\log(n/2)} = 1+ \frac{1}{x \log 2}, \\
x = \log_2 n &\quad\implies\quad \frac{n}{2^x} = 1 < 1+ \frac{1}{\log n} = 1+ \frac{1}{x \log 2},
\end{align*}
So $\log_2(n/2) < x_* < \log_2 n$. Using this, we obtain
$$ \max_{1\leq x \leq n} f_n(x) \leq \frac{e^{-1}}{(n/2) \log_2(n/2)} $$
Moreover, substituting $u = n/2^x$, or equivalently, $x = \log_2(n/u)$, we get
\begin{align*}
\int_{1}^{n} f_n(x) \, \mathrm{d}x
&= \int_{n/2^n}^{n/2} \frac{e^{-u}}{n \log(n/u)} \, \mathrm{d}u
= \frac{1}{n\log n} \int_{n/2^n}^{n/2} \frac{e^{-u}}{1 - \frac{\log u}{\log n}} \, \mathrm{d}u.
\end{align*}
It is not hard to show that this integral is asymptoticall $\frac{1}{n\log n}$ as $n \to \infty$. Combining altogether and letting $A_n = \left( n \log n \right) S_n$, we get
$$ 1 - \frac{2\log 2}{e} \leq \liminf_{n\to\infty} A_n \leq \limsup_{n\to\infty} A_n \leq 1 + \frac{2\log 2}{e}. $$
Since $\frac{2 \log 2}{e} \approx 0.509989$, this shows that $S_n = \Theta\left(\frac{1}{n\log n} \right) $.
(Simulation seems suggesting that $A_n$ actually converges as $n\to\infty$, but I will leave this question to others.)
