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