Asymptotic Value of a Function

Question

I am reading a paper and encountering an asymptotic expression:

$f(R)=\sum_{i=1}^{R} \binom{R}{i} (-1)^{i+1} \frac{1}{1-p^i}$

Then, the author says $O(f(R))=O\left(1+\frac{p\ln R}{1-p}\right)$. May I know how this asymptotic form is derived?

Answer 1

I assume $0<p<1$. For each $0<\varepsilon<1$ the asymptotic \begin{equation} f(R)\in O_\varepsilon\left(1+\frac{p\log(R)}{1-p}\right) \end{equation} holds for $\varepsilon<p<1$, but not for $0<p<1$. On the other hand $$f(R)\in O\left(1+\frac{\log(R)}{\log(1/p)}\right)$$ holds for $0<p<1$.

Start by writing: \begin{align*} f(R) &=\sum_{i=1}^{R} \binom{R}{i} (-1)^{i+1} \frac{1}{1-p^i}\\ &=\sum_{i=1}^{R} \binom{R}{i} (-1)^{i+1} \sum_{k=0}^\infty p^{ki}\\ &=-\sum_{k=0}^\infty\sum_{i=1}^{R} \binom{R}{i} (-p^k)^{i}\\ &=-\sum_{k=0}^\infty[(1-p^k)^R-1]\\ &=\sum_{k=0}^\infty[1-(1-p^k)^R] \end{align*} where \begin{align*} 0\leq &1-(1-p^k)^R\leq Rp^k&&k\in\Bbb N\\ 0\leq &1-(1-p^k)^R\leq 1&&k\in\Bbb N\\ \end{align*}

By taking $p=\frac 1{\sqrt R}$ we get $1-(1-p)^R\to 1$ and \begin{align*} \frac{f(R)(1-p)}{p\log(R)} &\geq \frac{(1-(1-p)^R)(1-p)}{p\log(R)}\\ &\sim\frac{\sqrt R}{\log(R)}\to\infty \end{align*} as $R\to\infty$, hence your asymptotic doesn't hold for $0<p<1$.

Now split the sum at $N$: \begin{align*} f(R) &=\sum_{k=0}^\infty[1-(1-p^k)^R]\\ &=\sum_{k=0}^{N-1}[1-(1-p^k)^R]+\sum_{k=N}^{+\infty}[1-(1-p^k)^R]\\ &\leq\sum_{k=0}^{N-1}1+\sum_{k=N}^{+\infty}Rp^k\\ &\leq N+Rp^{N}\sum_{i=0}^{+\infty}p^i\\ &\leq N+\frac{Rp^N}{1-p} \end{align*} We have $Rp^N\leq p\log(R)$ for $N\geq 1-\frac{\log\circ\log(R)}{\log(1/p)}+\frac{\log(R)}{\log(1/p)}$.

By taking $N=1+\lfloor \frac{\log(R)}{\log(1/p)}\rfloor$ we have $$f(R)\leq 1+\frac{\log(R)}{\log(1/p)}+\frac{p\log(R)}{1-p}$$ eventually for $R\to\infty$. But $$\frac p{1-p}\leq\frac 1{\log(1/p)}$$ hence $$f(R)\leq 1+\frac{2\log(R)}{\log(1/p)}$$ On the other hand, for $0<\varepsilon<p<1$ we have $1/\log(1/p)\in O_\varepsilon(p/(1-p))$ hence $$f(R)\in O_\varepsilon\left(1+\frac{p\log(R)}{1-p}\right)$$

Answer 2

Let $x_n$ denote the sum : $$x_n=\sum_{j=1}^{n}\binom{n}{j}\frac{\left(-1\right)^{j+1}}{1-p^j}.$$ For $p\in (0,1)$, we have $$\begin{align*} x_n& =\sum_{j=1}^n\binom{n}{j}\left(-1\right)^{n+1}\sum_{k=0}^{\infty}p^{kj}\\ & =-\sum_{k=0}^{\infty}\sum_{j=1}^n\binom{n}{j}\left(-p^k\right)^j\\ & =\sum_{k=0}^{\infty}\left[1-\left(1-p^k\right)^n\right]. \end{align*}$$ Clear that $1-\left(1-p^k\right)^n$ is decreasing for $x$, which implies that $$\begin{align*} I& :=\int_0^{\infty}\left(1-\left(1-p^x\right)^n\right)\text{d}x\\ & \leqslant x_n\leqslant I+1. \end{align*}$$ The substitution $y=1-p^x$ can get that $$\begin{align*} I& =\int_0^1\frac{y^n-1}{(1-y)\log p}\text{d}y\\ & =\frac{-1}{\log p}\int_0^1\left(1+y+\cdots+y^n\right)\text{d}y\\ & = -\frac{1+\frac{1}{2}+\cdots+\frac{1}{n}}{\log p}\sim -\frac{\log n}{\log p}. \end{align*}$$ Therefore, one can conclude that $$x_n\sim -\frac{\log n}{\log p},\ n\to \infty.$$ This more precise result can lead to what is desired.