Demostrar que $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $.

Question

Demostrar que $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $, con la inducción.

Tengo la intuición detrás de esta pregunta. Claramente, la función dada no está aún creciendo a una velocidad lineal, pero, ¿qué es el "adecuado" proofy manera de decir que el $ \displaystyle \sum_{k=1}^{n} \frac{1}{k} \leq \mathcal{O}(\log(n)) $? Yo era incapaz de encontrar cualquier útil identidades para el uso de dicha suma.

Answer 1

\begin{align} \sum_{k=1}^n\dfrac{1}{n}&\leq1+ \int_1^n\dfrac{1}{x}dx\\&=1+\log(x)\Big|_1^n\\&=1+\log(n)-\log(1)\\&=1+\log(n)\\&=\mathcal{O}(\log(n)) \end{align}

Answer 2

Usando la desigualdad de $1+x\le e^x$, podemos deducir $$ \log\left(\frac{n+1}{n}\right)=\log\left(1+\frac1n\right)\le\frac1n\le-\log\left(1-\frac1n\right)=\log\left(\frac{n}{n-1}\right)\tag{1} $$ Sumando $(1)$ rendimientos $$ \log(n+1)\le\sum_{k=1}^{n}\frac1k=1+\sum_{k=2}^{n}\frac1k\le1+\log(n)\etiqueta{2} $$ Es decir, para todos los $n\ge1$ $$ \log(n+1)\le\sum_{k=1}^{n}\frac1k\le1+\log(n)\etiqueta{3} $$

---

Las sumas pueden hacerse fácilmente en las inducciones. Vamos a probar a $(3)$ por inducción el uso de $(1)$.

Para $n=1$, $(3)$ sostiene desde $\log(2)\le1\le1$.

Supongamos que tenemos $(3)$$n-1$: $$ \log(n)\le\sum_{k=1}^{n-1}\frac1k\le1+\log(n-1)\etiqueta{4} $$ La desigualdad de $(1)$ dice que $$ \log\left(\frac{n+1}{n}\right)\le\frac1n\le\log\left(\frac{n}{n-1}\right)\etiqueta{5} $$ La adición de $(4)$ $(5)$rendimientos $$ \log(n+1)\le\sum_{k=1}^{n}\frac1k\le1+\log(n)\etiqueta{6} $$ que es$(3)$$n$. Esto termina la inducción.

Answer 3

Estoy ampliando la respuesta por xan:

Definir $H_n=\displaystyle\sum_{1\le k\le n} {1\over k}$, vamos a demostrar por inducción que $H_{2^n}\le n+1$. Esto es cierto para $n=0$ desde $H_{2^0}=H_1=1\le 1$.

Ahora supongamos $H_{2^n}\le n+1$. Tenemos:

$$\begin{align} H_{2^{n+1}} &= \sum_{1\le k\le 2^{n+1}} {1\over k} \\ H_{2^{n+1}} &= \sum_{1\le k\le 2^n} {1\over k} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over k} \\ H_{2^{n+1}} &= H_{2^n} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over k} \\ H_{2^{n+1}} &\le H_{2^n} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over 2^n} \\ H_{2^{n+1}} &\le H_{2^n} + (2^n-1){1\over 2^n} \\ H_{2^{n+1}} &\le H_{2^n} + (1-{1\over 2^n}) \\ H_{2^{n+1}} &\le H_{2^n} + 1 \\ H_{2^{n+1}} &\le (n+1) + 1 \\ H_{2^{n+1}} &\le n+2 \\ \end{align} $$

Ahora vamos a hacer $m=2^n$,$n=\lg m$, y:

$$H_{2^n}=H_m\le\lg m+1=\mathcal{O}(\log m)$$

Answer 4

Sugerencia: Piense en la integral de la $\displaystyle\int_1^n \frac{dx}x$.

Answer 5

Quiere mostrar que $\sum_{k=1}^{n} \frac{1}{k} \leq \mathcal{O}(\log(n))$. Esto significa que hay una constante $c > 0$ y un entero $n_0$ tal que $\sum_{k=1}^{n} \frac{1}{k} \leq c\log(n)$ para todos los $n \ge n_0$.

Supongamos que esto es cierto para algunos $n$$c$. Queremos mostrar que $\sum_{k=1}^{n+1} \frac{1}{k} \leq c\log(n+1)$ de la siguiente manera.

Por la hipótesis de inducción, $\sum_{k=1}^{n+1} \frac{1}{k} = \sum_{k=1}^{n} \frac{1}{k} + \frac1{n+1} \leq c \log(n) + \frac1{n+1} $ .

Si pudiéramos demostrar que $c \log(n) + \frac1{n+1} \le c \log(n+1)$, nos gustaría hacer. Pero $\log(n+1) - \log(n) = \log(1+1/n) > 1/n > 1/(n+1) $, así que esta desigualdad se cumple para cualquier $c \ge 1$.

Para encontrar un determinado $c$$n_0$, ver el $n = 3$. $1 + 1/2 + 1/3 < 2 < c \log 3$ for $c = 2$. Por lo $c=2$ va a trabajar.

Por supuesto, el mejor valor de $c$ 1, pero eso no es necesario para un $\mathcal{O}$ resultado - sólo necesita un poco de $c$.