# 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 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. Jan 31, 2018 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, 2018 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. Jan 31, 2018 at 11:36
• @Somos: I agree you have to solve for the $x$. However, according to the definition of recursion on wikipedia en.wikipedia.org/wiki/Recursion, both implicit and explicit functions (i.e. set of rules) are allowed to reduce "all other cases to the base case". Of course, the existence and uniqueness are part of a problem for recursion. But that is part and parcel of any mathematical problem.
– Hans
Jan 31, 2018 at 18:29
• @Somos: Particularly in the problem, had you read my linked original question and derivation therein, you would have found my current implicit formulation is much more conducive to the generating function treatment than your explicit one.
– Hans
Jan 31, 2018 at 18:29

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, 2018 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. Jan 31, 2018 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. Jan 31, 2018 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 Jan 31, 2018 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, 2018 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, 2018 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. Jan 31, 2018 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, 2018 at 18:13