Supongamos una secuencia real $1=a_1 \leq a_2 \le \cdots \leq a_n$ y $a_{i+1}-a_i \leq \sqrt {a_i}$ . ¿Esto se sostiene? $$ \sum_ {i=1}^{n-1} \frac {a_{i+1}-a_i}{a_i} \in O( \log n)$$
Respuesta
¿Demasiados anuncios?
Lema 1: Si $1 = a_1 \leq a_2 \leq a_3 \leq \cdots $ y $a_{i+1}-a_i \leq \sqrt {a_i}$ entonces $$ \sum_ {i=1}^{n-1} \frac {a_{i+1}-a_i}{a_i} = \Theta ( \log a_n) $$ para todos $n$ .
Prueba: Por las suposiciones que tenemos
$$ 0 \leq \frac {a_{i+1}-a_i}{a_i} \leq \frac {1}{ \sqrt {a_i}} \leq 1, $$
y desde que
$$ \frac {a_{i+1} - a_i}{a_i} = \frac {a_{i+1}}{a_i} - 1 \tag {1} $$
esto es equivalente a
$$ 1 \leq \frac {a_{i+1}}{a_i} \leq 2. \tag {2} $$
Si $1 \leq x \leq 2$ entonces
$$ \log x \leq x-1 \leq \frac { \log x}{ \log 2}, $$
así que el ajuste $x = a_{i+1}/a_i$ en las ecuaciones $(1)$ y $(2)$ rendimientos
$$ \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}. $$
Sumando esto en el rango $i=1,2, \ldots ,n-1$ rendimientos
$$ \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 $} $$
Lema 2: Si $a_i \geq 1$ y $a_{i+1}-a_i \leq \sqrt {a_i}$ entonces $1 \leq a_i \leq i^2+2$ .
Prueba: Resumiendo $a_{i+1}-a_i \leq \sqrt {a_i}$ sobre el rango $i=1,2, \ldots ,n-1$ rendimientos
$$ 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} $$
y por lo tanto
$$ a_i - i \sqrt {a_i} - 1 \leq 0. \tag {3} $$
La parábola $y = x^2 - ix - 1$ se encuentra debajo de la $x$ -eje para $1 \leq x \leq \frac {1}{2} \left (i + \sqrt {4 + i^2} \right )$ así que la ecuación $(3)$ combinado con la suposición $a_i \geq 1$ rendimientos
$$ 1 \leq a_i \leq \left ( \tfrac {i}{2} + \tfrac {1}{2} \sqrt {4 + i^2} \right )^2 \leq i^2 + 2, $$
donde la última desigualdad se deriva de la desigualdad de Jensen.
$$ \tag *{$ \square $} $$
Reclamar: Si $1 = a_1 \leq a_2 \leq a_3 \leq \cdots $ y $a_{i+1}-a_i \leq \sqrt {a_i}$ entonces $$ \sum_ {i=1}^{n-1} \frac {a_{i+1}-a_i}{a_i} = O( \log n) $$ para todos $n$ .
Prueba: El resultado es trivialmente cierto para $n=1$ así que supongamos $n \geq 2$ . Combinando los Lemmas 1 y 2 se obtiene
$$ 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 $$
para algunas constantes $C$ y $D$ .
$$ \tag *{$ \square $} $$
Intuición
La suma en cuestión se comporta de muchas maneras como un "logaritmo discreto", y en el sentido de Lemma 1 tenemos algo como
$$ \sum_ {i=1}^{n-1} \frac {a_{i+1}-a_i}{a_i} \approx \log \frac {a_n}{a_1}. $$
Por ejemplo, si duplicamos cada término de la secuencia $(a_n)$ entonces los valores a ambos lados de la $ \approx $ permanecen sin cambios. Además, si $a_n$ es la secuencia constante $a_n = a_1$ entonces ambos lados de la $ \approx $ son iguales.
(No estoy seguro de cuál es la analogía de $ \log xy = \log x + \log y$ sería.)
Podríamos intentar abordar este problema mirando los suaves análogos de la secuencia y la suma. La diferencia $a_{i+1} - a_i$ puede pensarse como un derivado discreto y la suma como una integral discreta. Así que si podemos encontrar alguna función $f$ con $f(n) \approx a_n$ y
$$ f'(n) \approx a_{n+1} - a_n $$
entonces podríamos esperar que
$$ \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}. $$
Esta observación fue lo que me llevó al enfoque de esta respuesta.
