7
$\begingroup$

This is a follow up of Limit of $S(n) = \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right)$

More details can be found in the above thread.

Let $S(n) = \displaystyle \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right)$

Mike has proved that $S(n)$ in fact diverges at-least faster than $\log_2(\lfloor n-1 \rfloor)$.

Now based on what Mike has worked this conjectures arises:

$\displaystyle \lim_{n \rightarrow \infty} (2 \log_{2}(n) - S(n)) = \alpha$.

Also, can $\alpha$ be expressed in terms of other familiar constants. $\frac{\pi \gamma}{e}$ seems to be a close guess.

The numerical evidence seem to suggest they are true. For example, we have the following graph of $2 \log_2 n - S(n)$ for $n \leq 300$.

alt text

(More numerical evidence: The value of $2 \log_2 n - S(n)$, is, for $n = 1000$, $2000$, and $3000$, respectively, $0.667734$, $0.667494$, and $0.667413$.)

An alternative expression for $S(n)$ was worked out by Moron in the previously-mentioned question:

$$S(n) = - \sum_{k=1}^{n-1} \frac{s(n,k)}{2^{n-k}-1},$$ where $s(n,k)$ is a Stirling number of the first kind.

  • 0
    @Sivaram: I added Moron's formula, so that it's not buried in the other question. I also added the combinatorics tag, as Stirling numbers are well-known combinatorial numbers, and someone may have some insight into $S(n)$ from that perspective.2010-11-24
  • 0
    @Mike: Sure. Feel free to edit it.2010-11-24
  • 0
    @Mike: In fact it might be of help if you could add the results/convergence plot you obtained as well.2010-11-24
  • 0
    @Mike: How did you get these results/plots ? What language did you use to code this up?2010-11-24
  • 2
    I would suggest not using `\displaystyle` in the title of the question, as it is still typeset as (very large) inline text and looks awkward on the front page.2010-11-24
  • 0
    @Rahul: Done...2010-11-24
  • 0
    @Sivaram: It's much better now. Thanks.2010-11-24
  • 0
    @Sivaram: I used Mathematica and Moron's formula for $S(n)$. Mathematica implements $s(n,k)$ as "StirlingS1[n, k]."2010-11-24
  • 0
    I think $\alpha$ (to six decimal places) is $0.667253$. I don't have time right now to explain why (I will try to update later today), but if this number is correct then the conjecture of $\pi \gamma / e$ is not right.2010-11-24
  • 0
    @Mike: I randomly googled and found this http://algo.inria.fr/csolve/erradd.pdf where the number you have quoted has appeared on page 30. I am reading through in what context and trying to make sense of it.2010-11-24
  • 0
    http://bootes.math.uqam.ca/cgi-bin/ipcgi/lookup.pl?Submit=GO+&number=0.667253&lookup_type=simple2010-11-25
  • 0
    I have a proof that (i) does actually converge. I will post it later tonight/tomorrow. Unfortunately, the proof gives no insight as to what $\alpha$ is.2010-11-25

2 Answers 2

8

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.


Part 1

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


Part 2

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


Part 3

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

  • 0
    Looks watertight. Maybe this should be a paper of some sort?2010-11-27
  • 0
    @Mike: I am reading through your proof. There is a typo in Part 1. $1 - \prod_{j=1}^{n-1} \left(1 - \frac{j}{2^k}\right) = 1$ when $k \leq \lfloor \log_2 (n-1) \rfloor$.2010-11-27
  • 0
    @Mike: Cool. Awesome! There were two cool things. First in part 2 approximating the product by exponential which helped. But the icing on the cake was to use Euler-Maclaurin summation in part 3!2010-11-27
  • 0
    @Mike: You would have probably noticed this already. By Euler-Maclaurin summation $\forall a>1$, we get $\sum_{m= - \infty}^{\infty} a^{-m} e^{-a^{-m}} = \frac{1}{\log a}$2010-11-27
  • 0
    @Mike: And you would also realized that the same line of argument will work for $\sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{a^k}\right)\right)$ where $a > 1$ giving rise to $alog_a n - \alpha_a$2010-11-27
  • 0
    +1: I've just read through the outline of your proof and it looks like you've nailed that constant. Further work along the lines in my post already had me thinking that the constant was probably the sum of some series in reciprocal powers of e, so your result is no surprise. Well done!2010-11-27
  • 0
    @Sivaram: Thanks for the correction. I'll fix it. I had thought about the generalizations, but it's good to point them out specifically.2010-11-27
  • 0
    @J.M.: If I were to turn this into a paper, do you have a suggestion for an appropriate journal?2010-11-27
3

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.

  • 0
    Good One!2010-11-27