Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
btw, how did you come up with the exact fractions? –  Aryabhata Nov 23 '10 at 23:45
    
@Moron: I worked out to find the pattern –  user17762 Nov 23 '10 at 23:49
    
@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. –  user17762 Nov 23 '10 at 23:53
    
@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! –  Aryabhata Nov 23 '10 at 23:53
    
@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. –  user17762 Nov 23 '10 at 23:54
show 4 more comments

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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! –  user17762 Nov 24 '10 at 6:55
    
The next question: Can my conjectured upper bound be proved? –  Mike Spivey Nov 24 '10 at 6:58
    
And $\alpha$ has to be $\gamma$ + 0.09 :-) (where $\gamma$ is the Euler constant). –  user17762 Nov 24 '10 at 7:01
2  
@Mike: You will be surprised by this!!! $\frac{\pi \gamma}{e} = 0.667103931...$ –  user17762 Nov 24 '10 at 7:34
2  
@Sivaram: Wow. I am torn between "surely that's just a coincidence" and "I don't believe in coincidences in mathematics." –  Mike Spivey Nov 24 '10 at 16:53
show 4 more comments

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

share|improve this answer
3  
@Moron: The coefficients are Stirling numbers of the first kind: en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind –  Mike Spivey Nov 23 '10 at 23:36
    
@Mike: Thanks, I have updated the answer with that information. –  Aryabhata Nov 23 '10 at 23:44
    
@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|$. –  user17762 Nov 24 '10 at 0:53
    
@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$. –  Mike Spivey Nov 24 '10 at 1:04
    
@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. –  user17762 Nov 24 '10 at 1:11
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.