Finding "growth" rate of a sum

Question

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?

Answer 1

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} \,.$$

Answer 2

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

1. $|f_n|\leq1$
2. $\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$.

Answer 3

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.

Answer 4

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