Limit of $S(n) = \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right)$ - Part II

Here's a proof. The value of $\alpha$ is the value of the infinite sum $$\sum_{m= -\infty}^{\infty} (e^{-2^{-m-1}} - [m \geq 1]),$$ where $[m \geq 1]$ is 1 if $m \geq 1$ and 0 otherwise. Mathematica gives this value (to 6 decimal places) as $0.667253$.

The full argument in all its rigor is too long to post on this site, so I'm only going to give an extended outline. There are a couple of strange claims in here, but bear with me.

From my previous post we know that $1 - \prod_{j=1}^{n-1} \left(1 - \frac{j}{2^k}\right) = 1$ when $k \leq \lfloor \log_2 (n-1) \rfloor$.

Let $p = 2 \log_2 n - \lfloor 2 \log_2 n \rfloor$. Thus $2 \log_2 n - S(n)$ is $$2 \log_2 n - \lfloor 2 \log_2 n \rfloor + \sum_{k= \lfloor \log_2 (n-1) \rfloor +1}^{\lfloor 2 \log_2 n \rfloor} \prod_{j=1}^{n-1} \left(1 - \frac{j}{2^k}\right) + \sum_{k= \lfloor 2 \log_2 n \rfloor + 1}^{\infty} \left(\prod_{j=1}^{n-1} \left(1 - \frac{j}{2^k}\right) - 1\right)$$ $$= p + \sum_{k= \lfloor \log_2 (n-1) \rfloor +1}^{2 \log_2 n - p} \prod_{j=1}^{n-1} \left(1 - \frac{j}{2^k}\right) + \sum_{k= 2 \log_2 n - p + 1}^{\infty} \left(\prod_{j=1}^{n-1} \left(1 - \frac{j}{2^k}\right) - 1\right) .$$

Now, the expression $$\prod_{j=1}^{n-1} \left(1 - \frac{j}{2^k}\right)$$ is very close to 0 when $k < 2 \log_2 n$ and very close to 1 when $k > 2 \log_2 n$. So most of the contribution to $2 \log_2 n - S(n)$ occurs when $k$ is close to $2 \log_2 n$. The next step, then, is to reindex with $m = k - \lfloor 2\log_2 n \rfloor$. Now we basically have $$2 \log_2 n - S(n) = p + \sum_{m= - \log_2 n}^0 \prod_{j=1}^{n-1} \left(1 - \frac{j}{2^{m-p} n^2}\right) + \sum_{m= 1}^{\infty} \left(\prod_{j=1}^{n-1} \left(1 - \frac{j}{2^{m-p} n^2}\right) - 1\right).$$

Next, we need a good approximation to $\prod_{j=1}^{n-1} \left(1 - \frac{j}{2^{m-p} n^2}\right)$. It turns out that $e^{-2^{-m+p-1}}$ is an excellent approximation (which surprises me some - despite the fact that I have verified it numerically - as it is independent of $n$). To see this, rewrite $\prod_{j=1}^{n-1} \left(1 - \frac{j}{2^{m-p} n^2}\right)$ as $$\exp \left( \sum_{j=1}^{n-1} \ln\left(1 - \frac{j}{2^{m-p} n^2}\right)\right)$$ and then expand the $\log$ expression with the Maclaurin series for $\ln (1+x)$. The first term in the expansion dominates when $m$ is positive or constant, and we get $$\prod_{j=1}^{n-1} \left(1 - \frac{j}{2^{m-p} n^2}\right) = \exp \left(\sum_{j=1}^{n-1} \left(- \frac{j}{2^{m-p} n^2} \right) + O\left(\frac{j^2}{4^{m-p} n^4}\right) \right)$$ $$=\exp \left( - \frac{1}{2^{m-p+1}} + O\left(\frac{1}{2^m n}\right) \right) = \exp \left( - \frac{1}{2^{m-p+1}}\right) + O\left(\frac{1}{2^m n}\right)$$ Thus $$\sum_{m= 1}^{\infty} \left(\prod_{j=1}^{n-1} \left(1 - \frac{j}{2^{m-p} n^2}\right) - 1\right) = \sum_{m= 1}^{\infty} \left(\exp \left( - \frac{1}{2^{m-p+1}} \right) - 1\right) + O\left(\frac{1}{n}\right).$$

When $m$ is negative and not constant, things are a little trickier, as the higher-order Maclaurin series terms make $\exp \left( - \frac{1}{2^{m-p+1} } \right)$ not a good relative approximation to the product. However, all the terms in the Maclaurin series are negative, so truncating after the first term does yield an upper bound. In addition, $\exp \left( - \frac{1}{2^{m-p+1}} \right)$ goes to zero extremely fast as $m \to -\infty$. (For example, if $m = - \log_2 (\log n)$ (which heads to $-\infty$ very slowly), we still have $\exp \left( - \frac{1}{2^{m-p+1}} \right) = \frac{1}{n^{2^{p-1}}}$.) Thus $\exp \left( - \frac{1}{2^{m-p+1}} \right)$ is still an excellent absolute approximation for the product when $m$ is negative. Since there are only $\log_2 n$ negative terms in the sum we are considering, we have $$\sum_{m= - \log_2 n}^0 \prod_{j=1}^{n-1} \left(1 - \frac{j}{2^{m-p} n^2}\right) = \sum_{m = - \log_2 n}^0 \exp \left( - \frac{1}{2^{m-p+1}} \right) + E(n),$$ where $E(n) \to 0$ as $n \to \infty$.

Now, let $$f(p) = \sum_{m= - \infty}^0 e^{-2^{-m+p-1}} + \sum_{m= 1}^{\infty} (e^{-2^{-m+p-1}} - 1).$$ The function $f$ is linear in $p$! (Despite having verified this numerically and despite the argument below, this still seems weird to me!) The slope is $-1$. To see this, differentiate to get $$f'(p) = - \ln 2 \sum_{m= - \infty}^{\infty} 2^{-m+p-1} e^{-2^{-m+p-1}}.$$

Now, apply the Euler-Maclaurin summation formula. Because we have the product of two exponentials, $f^{(k)}(p)$ will have the expression $2^{-m+p-1} e^{-2^{-m+p-1}}$ in every term. As $m \to \infty$, $2^{-m+p-1} \to 0$ and $e^{-2^{-m+p-1}} \to 1$. As $m \to -\infty$, $2^{-m+p-1} \to \infty$ and $e^{-2^{-m+p-1}} \to 0$, but the latter expression dominates. Thus $f^{(k)}(p) \to 0$ as $m \to \infty$ and as $m \to -\infty$. Thus the Euler-Maclaurin formula says that
$$f'(p) = - \ln 2 \int_{-\infty}^{\infty} 2^{-m+p-1} e^{-2^{-m+p-1}} dp = \left. e^{-2^{-m+p-1}}\right|_{-\infty}^{\infty} = -1.$$

Therefore, $$\lim_{n \to \infty} \left(2 \log_2 n - S(n)\right) = p + \sum_{m= - \infty}^0 e^{-2^{-m+p-1}} + \sum_{m= 1}^{\infty} (e^{-2^{-m+p-1}} - 1) $$ $$= p - p + \sum_{m= - \infty}^0 e^{-2^{-m-1}} + \sum_{m= 1}^{\infty} (e^{-2^{-m-1}} - 1) = \sum_{m= - \infty}^0 e^{-2^{-m-1}} + \sum_{m= 1}^{\infty} (e^{-2^{-m-1}} - 1).$$ Again, this value is approximately $0.667253$.

Here's an argument that pushes the lower bound for $S(n)$ closer to a factor of $2$ times $\log_2 n.$ More precisely, we show

$$ S(n) \ge \left( 2 - \frac{1}{e} \right) \left( \lfloor \log_2 n \rfloor – 1 \right). $$

Let $ a= \lfloor \log_2 n \rfloor $ and write $ f(n,x) = 1 - \prod_{j=1}^{n-1} ( 1 – jx),$ and so

$$ S(n) = \sum_{k=1}^\infty \left( 1 - \prod_{j=1}^{n-1} \left( 1 - \frac{j}{2^k} \right) \right)$$ $$ = \sum_{k=1}^\infty f(n, \frac{1}{2^k} ) = a-1 + \sum_{k=a}^\infty f(n, \frac{1}{2^k} ),$$

since for each $k \le a-1$ $\exists$ $j=2^k$ in $\prod_{j=1}^{n-1} ( 1 - j/2^k ),$ and thus this product is $0.$

So neglecting terms with $k \ge 2a-1,$ we have

$$S(n) \ge a-1 + \sum_{k=a}^{2a-2} f(n, \frac{1}{2^k} ). \qquad (1)$$

By the AM-GM for $x \le 1/(m-1)$ we have for $m \ge 2$ and $2/m(m-1) \le x \le 1/(m-1)$

$$(1-x)(1-2x) \cdots (1-(m-1)x) \le \left( 1 - \frac{mx}{2} \right)^{m-1} \le \left( 1 - \frac{1}{m-1} \right)^{m-1} < \frac{1}{e}. $$

Thus for $k=a, a+1,\ldots, 2a-2$ we have

$$ f(n, \frac{1}{2^k} ) \ge 1 - \frac{1}{e}$$

and substituting this into $(1)$ the result follows.