# Asymptotic value of a sequence

Assume a real sequence $1=a_1\leq a_2\le \cdots \leq a_n$, and $a_{i+1}-a_i\leq \sqrt{a_i}$. Does this hold: $$\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \in O(\log n)$$

• Let $a_i=i$ what happen? – Nosrati Jan 20 '17 at 21:52
• in that case, yes. But in general, is that true? – Liam_math Jan 20 '17 at 21:59

Lemma 1: If $1 = a_1 \leq a_2 \leq a_3 \leq \cdots$ and $a_{i+1}-a_i \leq \sqrt{a_i}$ then $$\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} = \Theta(\log a_n)$$ for all $n$.

Proof: By the assumptions we have

$$0 \leq \frac{a_{i+1}-a_i}{a_i} \leq \frac{1}{\sqrt{a_i}} \leq 1,$$

and since

$$\frac{a_{i+1} - a_i}{a_i} = \frac{a_{i+1}}{a_i} - 1 \tag{1}$$

this is equivalent to

$$1 \leq \frac{a_{i+1}}{a_i} \leq 2. \tag{2}$$

If $1 \leq x \leq 2$ then

$$\log x \leq x-1 \leq \frac{\log x}{\log 2},$$

so setting $x = a_{i+1}/a_i$ in equations $(1)$ and $(2)$ yields

$$\log \frac{a_{i+1}}{a_i} \leq \frac{a_{i+1} - a_i}{a_i} \leq \frac{1}{\log 2} \log \frac{a_{i+1}}{a_i}.$$

Summing this over the range $i=1,2,\ldots,n-1$ yields

$$\log \frac{a_n}{a_1} \leq \sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \leq \frac{1}{\log 2} \log \frac{a_n}{a_1}.$$

$$\tag*{\square}$$

Lemma 2: If $a_i \geq 1$ and $a_{i+1}-a_i \leq \sqrt{a_i}$ then $1 \leq a_i \leq i^2+2$.

Proof: Summing $a_{i+1}-a_i \leq \sqrt{a_i}$ over the range $i=1,2,\ldots,n-1$ yields

$$a_i - 1 = \sum_{j=1}^{i-1} (a_{j+1} - a_j) \leq \sum_{j=1}^{i-1} \sqrt{a_i} \leq i\sqrt{a_i}$$

and hence

$$a_i - i\sqrt{a_i} - 1 \leq 0. \tag{3}$$

The parabola $y = x^2 - ix - 1$ lies below the $x$-axis for $1 \leq x \leq \frac{1}{2}\left(i + \sqrt{4 + i^2}\right)$, so equation $(3)$ combined with the assumption $a_i \geq 1$ yields

$$1 \leq a_i \leq \left(\tfrac{i}{2} + \tfrac{1}{2}\sqrt{4 + i^2}\right)^2 \leq i^2 + 2,$$

where the last inequality follows from Jensen's inequality.

$$\tag*{\square}$$

Claim: If $1 = a_1 \leq a_2 \leq a_3 \leq \cdots$ and $a_{i+1}-a_i \leq \sqrt{a_i}$ then $$\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} = O(\log n)$$ for all $n$.

Proof: The result is trivially true for $n=1$ so suppose $n \geq 2$. Combining Lemmas 1 and 2 yields

$$0 \leq \sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \leq C\log a_n \leq C\log(n^2+2) \leq D \log n$$

for some constants $C$ and $D$.

$$\tag*{\square}$$

Intuition

The sum in question behaves in many ways like a "discrete logarithm", and in the sense of Lemma 1 we have something like

$$\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \approx \log \frac{a_n}{a_1}.$$

For example, if we double every term of the sequence $(a_n)$ then the values on both sides of the $\approx$ remain unchanged. Further, if $a_n$ is the constant sequence $a_n = a_1$ then both sides of the $\approx$ are equal.

(I'm not sure what the analogue of $\log xy = \log x + \log y$ would be.)

We could try to approach this problem by looking at the smooth analogues of the sequence and sum. The difference $a_{i+1} - a_i$ can be thought of as a discrete derivative and the sum as a discrete integral. So if we can find some function $f$ with $f(n) \approx a_n$ and

$$f'(n) \approx a_{n+1} - a_n$$

then we might expect that

$$\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} \approx \int_1^n \frac{f'(x)}{f(x)}\,dx = \log \frac{f(n)}{f(1)} \approx \log \frac{a_n}{a_1}.$$

This observation was what lead me to the approach in this answer.

• More generally, if (1) $0 < a_1 \leq a_2 \leq a_3 \leq \cdots$, (2) $a_{n+1} = O(a_n)$, and (3) there is a constant $d$ such that $a_n = O(n^d)$, then $$\sum_{i=1}^{n-1} \frac{a_{i+1}-a_i}{a_i} = O(\log n).$$ – Antonio Vargas Jan 21 '17 at 12:52