Asymptotics of $1-\prod\limits_{i=0}^{k-1}\left(1-\frac{i}{2^k}\right)$

Question

I am interested in the asymptotics of $$1-\prod_{i=0}^{k-1}\left(1-\frac{i}{2^k}\right).$$ As a rough piece of mostly incorrect work this looks a little like $$1-\prod_{i=0}^{k-1}e^{-i/2^k} = 1-e^{-k(k-1)/2^{k+1}} \approx \frac{k(k-1)}{2^{k+1}}.$$

Answer 1

Your "mostly incorrect work" is actually pretty sound. To see this, first prove by induction over $k\geqslant0$ that for every $a_i$ in $[0,1]$, $$1-s_k\leqslant\prod_{i=0}^{k-1}\left(1-a_i\right)\leqslant1-s_k+s_k^2,\quad \text{where}\quad s_k=\sum_{i=0}^{k-1}a_i. $$ Then apply this double inequality to $a_i=i/2^k$ and use the fact that in this case $s_k=k(k-1)/2^{k+1}$. Thus, $$ \frac{k(k-1)}{2^{k+1}}-\left(\frac{k(k-1)}{2^{k+1}}\right)^2\leqslant1-\prod_{i=0}^{k-1}\left(1-\frac{i}{2^k}\right)\leqslant\frac{k(k-1)}{2^{k+1}}. $$ When $k\to\infty$, $s_k\to0$ hence all these are equivalent to $s_k=k(k-1)/2^{k+1}$.

Answer 2

To approximate the product, we approximate its log, so $$\sum_{i=0}^{k-1} \log(1-i/2^k) \sim \int_0^{k-1} \log(1-x/2^{k}) d x= 2^k k \log (2)-(k-1) (k \log (2)+1)+\left(k-2^k-1\right) \log \left(-k+2^k+1\right).$$

Then, exponentiate back, and you should be good to go (you have to be careful about how closely the integral approximates the sum, but this particular function is decreasing convex, so it should be easy).