Por qué $\sum\limits_{i=1}^n \frac{1}{i} =\mathcal O(\ln(n))$ ?

Question

Estoy leyendo una prueba de libro de texto sobre algoritmos que utiliza este hecho:

$$\sum_{i=1}^n \frac{1}{i} =\mathcal O(\ln(n)).$$

¿Por qué es eso cierto? Estoy tratando de usar la serie Taylor para averiguar por qué, pero no estoy haciendo mucho progreso.

Answer 1

Para toda función no creciente $u$ y cada $k$ , $$ \int_{k}^{k+1}u(x)\,\mathrm dx\leqslant u(k)\leqslant \int_{k-1}^ku(x)\,\mathrm dx, $$ por lo que $$ \int_1^{n+1}u(x)\,\mathrm dx\leqslant\sum_{k=1}^nu(k)\leqslant u(1)+\int_1^nu(x)\,\mathrm dx. $$ Si $u:x\mapsto1/x$ el RHS es $1+\log n$ y el LHS es $\log(n+1)$ por lo tanto, para cada $n\geqslant1$ , $$ \log n\leqslant\sum_{k=1}^n\frac1k\leqslant1+\log n. $$ La suma en el medio se llama $H_n$ el $n$ número armónico y se sabe que, cuando $n\to\infty$ , $H_n-\log n\to\gamma$ la constante de Euler con $\gamma\approx0.577$ .

Answer 2

Usar la serie Taylor es trabajar demasiado. Recordemos la definición de $\ln$ (o, al menos, una propiedad): $$\ln(x) = \int_1^x \frac 1xdx$$ Si $x \in \Bbb N$ también tenemos por la definición de la integral $$\int_1^x \frac 1x dx \geq \sum_{n=2}^x \frac 1n$$

Puede verlo gráficamente aquí (imagen robada de Apuntes de matemáticas en línea de Paul ):

También tenemos $\sum_{n=2}^x \frac 3n \geq \sum_{n=1}^x \frac 1n$ para $n \in \Bbb N$ (que se puede demostrar por inducción o de otro modo), de modo que $$3\ln(x) \geq \sum_{n=1}^x \frac 1n$$ y por lo tanto $\sum_{n=1}^x \frac 1n = O(\ln(x))$ como se desee.