2
$\begingroup$

In his answer to this question seeking the asymptotics of $$a_n = 1+\frac1{2^n}\sum_{k=0}^n {n\choose k}a_k,\, \forall n\in\mathbf N,\, a_0=0.$$ for $n\to\infty$, @JackD'Aurizio continued my approach and provided two summation expressions $$a_s=\sum_{m=1}^{s}\binom{s}{m}\frac{(-1)^{m+1}}{1-\frac{1}{2^m}}=\sum_{k\geq 1}\left[1-\left(1-\frac{1}{2^k}\right)^s\right].$$ Approximating $1-\frac{1}{2^k}\approx e^{-\frac1{2^k}}$ and subsequently $a_s$ with $b_s$ where $$b_{2s}-b_s = 1-e^{-s} \approx 1,$$ We obtain heuristically $$a_s \approx b_s\approx D+\log_2s,$$ for some constant $D$.

However, both of us failed to prove this heuristic result. I am hereby seeking a rigorous proof.

$\endgroup$
4
  • $\begingroup$ Is the $a_n$ on the left the same as the $a_n$ on the right? Otherwise, this looks like the Euler Series Transformation except for a missing $(-1)^k$ $\endgroup$ – robjohn Jan 29 '18 at 23:36
  • $\begingroup$ @robjohn: Yes, they are the same. It does like similar, except the sign and the diatic coefficient in the front. $\endgroup$ – Hans Jan 29 '18 at 23:40
  • $\begingroup$ I can't prove $a_s=\log_2s+O(1)$, but $a_s\sim\log_2s$ would be possible (though rather technical, not very elegant). Would that be of interest for you? $\endgroup$ – user436658 Feb 3 '18 at 19:56
  • $\begingroup$ @ProfessorVector: Yes. $\endgroup$ – Hans Feb 4 '18 at 0:40
2
$\begingroup$

A quick computation. We show that $a_n = \log_2 n + \mathcal{O}(1)$. Notice that $x \mapsto 1 - (1-2^{-x})^n$ is decreasing in $x$ for each $n \geq 1$. So

$$ a_n = \sum_{j=0}^{\infty} (1 - (1 - 2^{-j})^n) \leq 1 + \int_{0}^{\infty}(1 - (1 - 2^{-x})^n) \, dx = 1 + \frac{H_n}{\log 2}, $$

where $H_n = \sum_{k=1}^{n} \frac{1}{k}$ is the harmonic numbers and the integral is computed using the substitution $u = 1-2^{-x}$. A lower bound is obtained in a similar way:

$$ a_n \geq \int_{0}^{\infty}(1 - (1 - 2^{-x})^n) \, dx = \frac{H_n}{\log 2}. $$


More detailed result. Write $F_{n}(x) = (1 - 2^{-x})^n$. Using Euler-MacLaurin formula, we find that

$$ a_n = \frac{H_n}{\log 2} + \frac{1}{2} - \int_{0}^{\infty} \tilde{B}_1(x) \, dF_n(x), $$

where $\tilde{B}_1(x)$ is the periodic Bernoulli polynomial of degree 1. Notice that the bound $|\tilde{B}_1(x)| \leq \frac{1}{2}$ replicates the previous inequalities.

Now let $X_i \sim \mathrm{Exp}(\log 2)$ be i.i.d. and $M_n = \max\{X_1, \cdots, X_n\}$. Then $\mathbb{P}[M_n \leq x] = F_n(x)$ and $M_n - \log_2 n \Rightarrow G$, where $G$ satisfies $\mathbb{P}[G \leq x] = \exp(-2^{-x})$. From this, we may expect that

\begin{align*} a_{n} &= \frac{H_{n}}{\log 2} + \frac{1}{2} - \mathbb{E}[\tilde{B}_1(M_{n})] \\ &= \frac{H_{n}}{\log 2} + \frac{1}{2} - \mathbb{E}[\tilde{B}_1(G + \log_2 n)] + o(1) \end{align*}

holds. Indeed this is not terribly hard to establish using the continuous mapping theorem. Finally, numerical computations suggests that $\alpha \mapsto \mathbb{E}[\tilde{B}_1(G + \alpha)]$ is quite small (of order $10^{-6}$) but not identically zero, hence $a_n$ should exhibit an oscillation which slows down at logarithmic speed.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.