5
$\begingroup$

This is a follow up of Upper bound binomial sum

I was working on the problem in the above thread and noticed an interesting thing. I wanted to try and improve the bound Derek had (which was a quadratic in $n$).

If we reformulate the problem as Derek has (since for this we need $2^k \geq n$, so we forget the original problem and think the problem given is as follows)

i.e.

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

We see that

$S(1) = 0$

$S(2) = 1$

$S(3) = \frac{7}{3} \approx 2.3333$

$S(4) = \frac{67}{21} \approx 3.1904$

$S(5) = \frac{407}{105} \approx 3.8762$

$S(6) = \frac{4789}{1085} \approx 4.4138$

$S(7) = \frac{5289}{1085} \approx 4.8747$

$S(8) = \frac{726093}{137795} \approx 5.2694$

$S(9) = \frac{118399669}{21082635} \approx 5.61598$

$S(10) = \frac{9120486643}{1539032355} \approx 5.92612$

$S(11) = \frac{105065594573}{16929355905} \approx 6.20612$

$S(12) = \frac{31986101239583}{4950627362505} \approx 6.4610$

We see that the growth is slow as $n$ increases. My question is if this converges to some limit or it diverges. I have been working on it for the past couple of hours but am unable to come to a conclusion.

So the question is what is $\displaystyle \lim_{n \rightarrow \infty} S(n)$?

If it converges, can we find the limit?

or

If it diverges, how fast does it diverge?


$\textbf{EDIT:}$

So Mike has proved that $S(n)$ in fact diverges.

The conjecture is now that $\lim_{n \rightarrow \infty} (2 \log_{2}(n) - S(n)) = \alpha$ where $\alpha \approx 0.667$.

Look at 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 for further discussions.

  • 0
    @SIvaram: The link to Part II is really annoying. Can you please make it smaller? And please, keep the updates at the end. If someone is reading it for the first time, they will find it really abrupt.2010-11-24

2 Answers 2

4

$S(n)$ diverges at a rate at least as large as $\log_2 n$.

Suppose $n > 2^k$. Then, for some $1 \leq j \leq n-1$, $j = 2^k$. Thus $\prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right) = 0.$

Therefore, $S(n) = \sum_{k=1}^{\infty} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right) > \sum_{k=1}^{\log_2 (n-1)} \left(1 - \prod_{j=1}^{n-1}\left(1-\frac{j}{2^k}\right)\right) = \sum_{k=1}^{\log_2 (n-1)} 1 = \lfloor \log_2 (n-1) \rfloor.$


As far as an upper bound, the following graph is of $2 \log_2 n - S(n)$ for $n \leq 300$. I conjecture that there exists some $\alpha \approx \frac{2}{3}$ such that $S(n) \leq 2 \log_2 n - \alpha$ for $n \geq 2$ and that $\lim_{n \to \infty} (2 \log_2 n - S(n)) = \alpha$.

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

  • 2
    @Sivaram: Wow. I am torn between "surely that's just a coincidence" and "I don't believe in coincidences in mathematics."2010-11-24
3

If $(x-1)(x-2)\cdots(x-(n-1)) = \sum_{j=0}^{n-1} a_j x^j$

(As Mike points out, the $a_j$ are nothing but Stirling Numbers of the first kind)

Then the $k^{th}$ term is $\displaystyle - \sum_{j=0}^{n-2} \frac{a_j}{2^{(n-1-j)k}}$

by setting $\displaystyle x=2^k$ in the above polynomial and dividing by an appropriate power of $2$.

And so the limit is

$S(n) = \displaystyle - \sum_{j=0}^{n-2} \frac{a_j}{2^{n-1-j}-1}$

For example, for $\displaystyle n=5$, we have

$\displaystyle (x-1)(x-2)(x-3)(x-4) = x^4 - 10x^3 + 35x^2 - 50x + 24$.

Thus

$\displaystyle S(5) = 10/1 - 35/3 + 50/7 - 24/15 = 407/105$.

  • 0
    @Sivaram: I haven't thought it through myself; I was just responding directly to your statement that you were unable to bound $|\sum_{j=0}^{n-2} a_j|$. You might be right that that's not sufficient.2010-11-24