Finding "growth" rate of a sum Question
Let $n$ be a positive integer. The sum in question is: $$S_n=\sum_{i=1}^{ n}\frac{1}{2^i}\bigg(1-\frac{1}{2^{i}}\bigg)^{n}.$$ Clearly this sum is convergent, and it seems like the sum goes to $0$ as $n$ goes to infinity. Testing for $n<2000$ it seems like $S_n$ "grows" (decays) like $1/n$ asymptotically. So I am currently trying to upper bound $S_n$ by $c/n$ for some constant $c>0$.
Attempt
Pick a constant $d \in(0,1)$. Then for $i \leq d \log_2(n)$ one can easily show that: $$\big(1-2^{-i}\big)^n$$ tends to $0$ exponentially quickly with respect to $n$. So we can disregard the first bit of the sum and focus on: $$\sum_{i=\lfloor d\log_2(n)\rfloor+1}^{ n}\frac{1}{2^i}\bigg(1-\frac{1}{2^{i}}\bigg)^{n}.$$ We also clearly have that: $$\sum_{i=\lfloor \log_2(n) \rfloor}^n\frac{1}{2^i} \leq d'/n$$ for some $d'>0$.
But now we have to upper bound that middle portion of the sum, and using the methods I have used so far can give an upper bound that decays slower than $1/n$.
How do I proceed from here?
 A: Observe that for each $i \ge 1$, we have
$$ \int_{2^{-i}}^{2^{1-i}} (1-x)^n \,dx \le \frac{1}{2^{i}}\bigg(1-\frac{1}{2^{i}}\bigg)^{n} \le 2\int_{2^{-i-1}}^{2^{-i}} (1-x)^n \,dx \,,$$
so
$$\int_{2^{-n}}^{1} (1-x)^n \,dx  \le S_n=\sum_{i=1}^{ n}\frac{1}{2^i}\bigg(1-\frac{1}{2^{i}}\bigg)^{n} \le
2\int_{0}^{1} (1-x)^n \,dx \,.$$
By Bernoulli's inequality, $1-mt \le (1-t)^{m}$, we conclude that
$$\frac{ 1-(n+1)2^{-n}  }{n+1} \le \frac{(1-2^{-n})^{n+1}}{n+1} \le S_n \le \frac{2}{n+1} \,.$$
A: Using the heuristic approach we can find the main asymptotics term of the sum (a more accurate analysis can also be done).
$$S_n=\sum_{k=1}^{ n}\frac{1}{2^k}\bigg(1-\frac{1}{2^k}\bigg)^{n}=\sum_{k=1}^{ n}e^{-k\ln2}e^{n\ln(1-\frac{1}{2^k})}$$
The first exponent declines at growing $k$, while the second - grows. There should be some minimum of $f(k)=-k\ln2+n\ln(1-\frac{1}{2^k})$, which is not too much close to $k=1$ or $k=n$ (the minimum evaluation gives $k_{\min}\approx \ln n$, what confirms the approach). For these $k$ (which make the biggest contribution to the sum) $\,\ln(1-\frac{1}{2^k})\approx-\frac{1}{2^k}$, and the sum can be presented in the form
$$S_n\approx\sum_{k=1}^{ n}e^{-k\ln2}e^{-\frac{n}{2^k}}=\sum_{k=1}^{ n}e^{-k\ln2-ne^{-k\ln2}}$$
With the accuracy up to exponentially small terms we can expand summation from $k=0$ to $k=\infty$. Switching from summation to integration and not keeping exponentially small terms
$$S_n\approx \int_0^\infty e^{-k\ln2-ne^{-k\ln2}}dk\approx\frac{1}{\ln2}\int_0^\infty e^{-t-ne^{-t}}dt=\frac{1}{\ln2}\int_0^1e^{-nx}dx\approx\frac{1}{(n+1)\ln2}$$
This is a rather good approximation. Making the numerical check with WolframAlpha
$$S_{1000}=0.00144127...$$
$$\frac{1}{(n+1)\ln2}\,\bigg|_{n=1000}=0.001441253...$$
$$S_{5000}=0.000288479...$$
$$\frac{1}{(n+1)\ln2}\,\bigg|_{n=5000}=0.00288481...$$
etc.
A: This is more a comment than a full solution and it only addresses the observation by the OP that the sequence $S_n$ seems to converge to $0$.
Define $f_n(j)=\big(1-2^{-j}\big)^n\mathbb{1}_{[1,n]}(j)$. Notice that

*

*$|f_n|\leq1$

*$\lim_nf_n(j)=0$ for all $j\in\mathbb{N}$.
Dominated convergence implies that
$$\lim_n\sum^\infty_{j=1}f_n(j)2^{-j}=\sum^\infty_{j=1}\lim_nf_n(j)\,2^{-j}=0$$
Comment: Here, I use the measure $\mu(\{j\})=2^{-j}$ on the measurable space $(\mathbb{N},2^{\mathbb{N}})$. The constant function $g(j)\equiv1$ is integrabe with respect to $\mu$.
A: Compare $$S_n=\sum_{i=1}^{ n}x^i\,(1-x^i)^{n}\quad \text{and} \quad T_n=\int_1^n x^i\,(1-x^i)^{n}\,di$$
$$T_n=\frac{(1-x)^{n+1}-\left(1-x^n\right)^{n+1}}{(n+1) \log (x)}$$
Now, computing for $x=\frac 12$
$$\left(
\begin{array}{cc}
n & \Bigg| \frac {S_n-T_n} {S_n}\Bigg| \\
 1000 & 8.063 \times 10^{-6}\\
 2000 & 7.942 \times 10^{-6}\\
 3000 & 3.667 \times 10^{-6}\\
 4000 & 7.882 \times 10^{-6}\\
 5000 & 8.937 \times 10^{-6}\\
 6000 & 3.663 \times 10^{-6}\\
 7000 & 8.472 \times 10^{-6}\\
 8000 & 7.852 \times 10^{-6}\\
 9000 & 1.544 \times 10^{-6}\\
 10000 & 8.894 \times 10^{-6}
\end{array}
\right)$$
