7
$\begingroup$

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)$$

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

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.

$\endgroup$
  • $\begingroup$ 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).$$ $\endgroup$ – Antonio Vargas Jan 21 '17 at 12:52

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.