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
    btw, how did you come up with the exact fractions?2010-11-23
  • 0
    @Moron: I worked out to find the pattern2010-11-23
  • 0
    @Moron: Wait I am now feeding this in Mathematica for a generic $n$. Lets see what it gives. It doesn't give a closed form answer.2010-11-23
  • 0
    @Siva: So you have a guess as what the closed form formula is? Why don't you update the question with that? Perhaps someone can prove that using the stirling numbers in my answer. OEIS does not seem to have an entry for the numerator sequence you have!2010-11-23
  • 0
    @Moron: No. I dont have a closed form. Mathematica doesn't give the closed form. I did not know that these were Stirling numbers until Mike pointed it out.2010-11-23
  • 0
    @Moron: I calculated some more numbers using Mathematica and have updated the question2010-11-24
  • 0
    On the numerical front... have you tried a `ListPlot[]` of your numbers? If from plots you have reason to suspect that it *might* converge, then there is the function `SequenceLimit[]` ...2010-11-24
  • 0
    @J.M: I think it converges. We can prove it by alternating test since these coefficients (See Moron's answer) keep changing sign and the tail tends to zero. I need to look at it carefully though.2010-11-24
  • 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$.)

  • 0
    Well well... It now seems obvious that it should be greater than $\log_2(n-1)$! How often these things happens! When some one proves them and has the answer it seems straightforward!2010-11-24
  • 0
    The next question: Can my conjectured upper bound be proved?2010-11-24
  • 0
    And $\alpha$ has to be $\gamma$ + 0.09 :-) (where $\gamma$ is the Euler constant).2010-11-24
  • 0
    or is there any nice way to play around with $\pi$ and $e$ to get something close to $0.09$? :) :)2010-11-24
  • 0
    I am actually now surprised that you were able to come up with such a nice convergence estimate for $S(n)$. Your conjecture is something interesting and also the value of the limit will be interesting. Probably we can try the age old trick of trying to approximate the summation with integrals to get some sort of hold on this.2010-11-24
  • 0
    While we're guessing constants, $\ln 2 \approx 0.69$, which also looks suspicious. :)2010-11-24
  • 0
    I think your conjecture is worth a bounty. I will start a bounty sometime tomorrow or day-after. Till then let me give it a try.2010-11-24
  • 2
    @Mike: You will be surprised by this!!! $\frac{\pi \gamma}{e} = 0.667103931...$2010-11-24
  • 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$.

  • 3
    @Moron: The coefficients are Stirling numbers of the first kind: http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind2010-11-23
  • 0
    @Mike: Thanks, I have updated the answer with that information.2010-11-23
  • 0
    @Moron: $a_j$'s keep alternating sign and $\frac{1}{2^{n-j-1}-1}$ is a decreasing function. So if we could bound $|\displaystyle \sum_{j=0}^{n-2} a_j|$, then we use Generalized alternating test to prove that $S(n)$ converges. However, I am unable to bound $|\displaystyle \sum_{j=0}^{n-2} a_j|$.2010-11-24
  • 0
    @Sivaram: The row sums of the Stirling numbers of the first kind are known to be 0 for $n \geq 2$. Since we're adding up all of them but $s(n,n)$ we should have $|\sum_{j=0}^{n-2} a_j| = 1$.2010-11-24
  • 0
    @Mike: Right I thought about this but I am not completely sure if this will suffice for the alternating test since $a_j$ depends on $n$. We have $\displaystyle |\sum_{k=1}^{n-1}s(n,k)| = 1$. But don't we need something more like $\displaystyle |\sum_{k=1}^{n-1}s(m,k)|$ to be bounded irrespective of $m$. Sorry if I sound confusing.2010-11-24
  • 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