# Seeking proof to an asymptotics of a recursion or functional equation

My question on math.stackexchange.com and the continuation by an answer to it gives the two summation expressions for the recursion $$a_n = 1+\frac1{2^n}\sum_{k=0}^n {n\choose k}a_k,\, \forall n\in\mathbf N,\, a_0=0$$ as $$a_s=\sum_{m=1}^{s}\binom{s}{m}\frac{(-1)^{m+1}}{1-\frac{1}{2^m}}=\sum_{k=0}^\infty\left[1-\left(1-\frac{1}{2^k}\right)^s\right].$$ I am seeking an asymptotics to $a_n$ as $n\to\infty$. As stated in the aforementioned answer, numerical experiments suggest that $$a_s \approx A \log\left(B+Cs\right)\qquad \text{for }s\to +\infty$$ with $A\approx C\approx \sqrt{2}\approx\frac{1}{\log 2}$. 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, we failed to prove this heuristic result. I am seeking a rigorous proof.

We have now the excellent proofs below of Fedor Petrov and Iosif Pinelis. I then happened upon this exact same quesiton. It has its own answers and several related references. Here is another appearance of the same problem with many answers and references to powerful tools.

• I think you want $\sum_{k\ge 0} \left[ 1 - (1-1/2^k)^s\right]$. – Robert Israel Jan 30 '18 at 18:31
• @RobertIsrael: Yes, you are right. I have corrected it. Thank you. – Hans Jan 30 '18 at 19:18
• I suggest that $a_n = (\sum_{k=0}^{n-1} {n\choose k}(a_k+1))/(2^n-1),\, \forall n\in\mathbf N,\, a_0=0$ would be a better recursion because $a_n$ does not appear on the right side, while in your recursion it does. – Somos Jan 31 '18 at 4:34
• @Somos: You need to add a $1$ on your numerator. In any case, what is the difference? It is an equation for a recursion. Is there any essential difference between, say, $2x=x+1$ and $x=1$? – Hans Jan 31 '18 at 5:53
• @Hans, You are right about 1 in numberator. My typo. The difference is $2x=x+1$ you have to solve for $x$, in $x=1$ you don't. In almost all cases of recursions I have seen, you don't need to solve for $a(n)$. It is very unusual and unexpected to have to solve for $a(n)$. It is not immediately clear that a solution exists or is unique in general. – Somos Jan 31 '18 at 11:36

## 2 Answers

I claim that $$a_s=\log_2s+\frac\gamma{\log2}-\frac12+\log 2\int_{-\infty}^\infty\exp(-2^{-y})2^{-y}\left(\{y+\log_2s\}-\frac12\right)dy+o(1).$$ The integral term is a 1-periodic function of $\log_2 s$.

Denote $f(x)=1-(1-2^{-x})^s$. Then $f(0)=1,f(+\infty)=0$ and $f$ decreases on $[0,\infty)$. Thus $\sum_{k\geqslant 1} f(k)\leqslant \int_0^\infty f(x)dx\leqslant \sum_{k\geqslant 0} f(k)$. Look at the integral. Denote $1-2^{-x}=t$, then $t$ varies between 0 and 1. Next, $-x=\log(1-t)/\log 2$, so $dx=\frac{dt}{(1-t)\log 2}$ and the integral rewrites as $\frac1{\log2}\int_0^1\frac{1-t^s}{1-t}dt$. When $s$ is a positive integer, the integral equals $$\int_0^1 (1+t+t^2+\dots+t^{s-1}) dt=1+1/2+1/3+\dots+1/s=\log s+\gamma+o(1),$$ the same holds for non-integral $s$ by monotonicity in $s$. So we get $\sum_{k\geqslant 1} f(k)=\log_2 s+A(s)+o(1)$, where $$A(s)=\frac\gamma{\log 2}-\frac12+\sum_{k=1}^\infty\left( \frac{f(k-1)+f(k)}2-\int_{k-1}^kf(x)dx\right).$$ By Euler--Maclaurin integration by parts, we write $$\int_{k-1}^k f(x)dx=\int_{k-1}^k f(x)d\left(x-k+\frac12\right)=\frac{f(k-1)+f(k)}2-\int_{k-1}^k\left(x-k+\frac12\right)f'(x)dx.$$ Thus $$A(s)=\frac\gamma{\log 2}-\frac12+\int_0^\infty \left(\{x\}-\frac12\right)f'(x)dx.$$

Our goal is to estimate the last integral with prescribed accuracy $\varepsilon$. Choose large $M$, then the value $f(\log_2s\pm M)$ are close to 0 and 1, and we may choose $M$ so large that $f(\log_2s+M)+1-f(\log_2s-M)<\varepsilon/5$. Then the integral outside the segment $[\log_2s-M,\log_2s+M]$ is less than $\varepsilon/10$ in absolute value (we use $\int_{x_1}^{x_2}|f'(x)|dx=f(x_1)-f(x_2)$, that follows by monotonicity.) On the segment $[\log_2s-M,\log_2s+M]$ we use the change of variables $x=\log_2s+y$, $y\in [-M,M]$. Then $$-f'(x)=s(1-2^{-x})^{s-1}2^{-x}\log 2=\log 2\cdot 2^{-y}(1-s^{-1}2^{-y})^{s-1}.$$ Uniformly on $[-M,M]$ the expression $(1-s^{-1}2^{-y})^{s-1}$ is close for large $s$ to $e^{-2^{-y}}$. Therefore within another $\varepsilon/10$, the integral over $[\log_2s-M,\log_2s+M]$ is close to $$\log 2\int_{-M}^M 2^{-y}e^{-2^{-y}}\left(\{y+\log_2s\}-\frac12\right)dy.$$ The upper and lower limits may be replaced by $\pm \infty$ (within another $\varepsilon/10$), and we get the claim.

• Ah, excellent. The remainder which you denote as $O(1)$ includes more than the Euler–Mascheroni constant right as it actually is the difference between the infinite sum of $f(k)$ and the integral approximation, right? Yes, I would like to see the detail of the Euler-Maclaurin type argument. – Hans Jan 30 '18 at 19:07
• I am intrigued about the use of Euler--Maclaurin (EM) argument to find the presumed constant in $O(1)$ here. In known to me applications of the EM formula to the summation of series, the formula is applied -- not to the entire series -- but to a tail of it (to make the remainder in the EM formula small), and this is complemented by a direct calculation of the partial sum of the series without the mentioned tail; cf. the examples in arxiv.org/abs/1511.03247 . Thus, the EM formula acts as an accelerator of convergence/extrapolation device. – Iosif Pinelis Jan 31 '18 at 4:47
• Previous comment, continued: However, in the present case the partial sum depends on the parameter $s$, and so, I see no way to effectively compute the partial sum. – Iosif Pinelis Jan 31 '18 at 4:48
• @IosifPinelis we may apply Euler-Maclaurin to the whole series here, but it seems that I was wrong and there is no limit, see updated answer – Fedor Petrov Jan 31 '18 at 10:09
• +1. Excellent method. But would you mind explicating in detail your assertion "This suggest that the behaviour of $A(s)$ depends on arithmetical properties (concretely, fractional part) of $\log_2 s$, and so $A(s)$ does not have a limit!"? – Hans Feb 2 '18 at 8:09

Let $c_k:=(1-\frac1{2^k})^s$ and $b_k:=1-c_k$, so that \begin{equation} a_s=\sum_{k\ge0}b_k. \tag{1} \end{equation} Let $k_s:=\lceil \log_2 s\rceil$, so that $s/2^{k_s}\in[1/2,1]$. Clearly, $b_k\le1$, whence \begin{equation} \sum_0^{k_s}b_k\le k_s+1.\tag{2} \end{equation} On the other hand, $c_k\le d_k:=e^{-s/2^k}$ and the ratio $d_{j-1}/d_j=d_j$ is increasing in $j$, with $d_{k_s}\in[1/e,1/\sqrt e]$. So, majorizing $\sum_0^{k_s}d_k$ by a geometric series, we have \begin{equation} \sum_0^{k_s}c_k\le\sum_0^{k_s}d_k\le\frac{d_{k_s}}{1-d_{k_s}}=O(1). \tag{3} \end{equation} Also, $b_k\le\frac s{2^k}$ and hence \begin{equation} 0\le\sum_{k>k_s}b_k\le\sum_{k>k_s}\frac s{2^k}=\frac s{2^{k_s}}\le1. \tag{4} \end{equation} Collecting (1)--(4) and recalling that $b_k=1-c_k$, we have \begin{equation*} a_s=k_s+O(1)=\log_2 s+O(1). \end{equation*}

• Excellent! +1 Do you have any way to calculate (and prove) the smaller order terms of this sequence? – Hans Jan 31 '18 at 17:30
• @Hans : Considerations presented in the answer by Fedor Petrov appear to suggest that the behavior of the $O(1)$ term in the asymptotic relation $a_s=\log_2 s+O(1)$ depends on arithmetic properties of $\log_2 s$. Apparently, much more powerful tools are needed to adequately describe this behavior -- I have no good idea at the moment on how to proceed here. – Iosif Pinelis Jan 31 '18 at 21:54
• By the way, there is this question math.stackexchange.com/q/2611835/64809 and very impressive answer math.stackexchange.com/a/2623249/64809 of an inequality. Would you be interested in looking into whether you have a more straightforward proof? – Hans Feb 1 '18 at 18:13