Demostrar que $\log X < X$ para todos $X > 0$

Question

Estoy trabajando con Estructuras de Datos y Análisis de Algoritmos en C++, 2ª Ed, y el problema 1.7 nos pide que demostremos que $\log X < X$ para todos $X > 0$ .

Sin embargo, a no ser que me esté perdiendo algo, esto no se puede demostrar. El espíritu del problema sólo se mantiene si se definen varios calificativos adicionales, porque es relativamente fácil proporcionar contraejemplos.

En primer lugar, dice que $\log_{a} X < X$ para todos $X > 0$ En esencia.

Pero si $a = -1$ entonces $(-1)^{2} = 1$ . Por lo tanto, $\log_{-1} 1 = 2$ . Por lo tanto, debemos asumir $a$ es positivo.

si $a$ es $< 1$ entonces $a^2 < 1$ . Por lo tanto, debemos asumir que $a \geq 1$ .

Ahora bien, el libro dice que, a menos que se indique lo contrario, en general se habla de base 2 para los logaritmos, que son vitales en informática.

Sin embargo, incluso entonces - si $a$ es dos y $X$ es $\frac{1}{16}$ entonces $\log_{a} X$ es $-4$ . (De forma análoga, para la base 10, intente tomar el logaritmo de $\frac{1}{10}$ en su calculadora: Es $-1$ .) Por lo tanto, debemos suponer que $X \geq 1$ .

...A no ser que me esté perdiendo algo terriblemente. El problema parece bastante diferente si tenemos que probarlo para $X \geq 1$ .

Pero incluso así, necesito ayuda para resolver el problema. He intentado manipular la ecuación de todas las formas que se me han ocurrido pero no lo consigo.

Answer 1

Una forma de abordar esta cuestión es considerar el mínimo de $x - \log_a x$ en el intervalo $(0,\infty)$ . Para ello podemos calcular la derivada, que es $1 - 1/(\log_e a )\cdot x$ . Por tanto, la derivada es cero en un único punto, a saber $x = 1/\log_e a,$ y es negativo a la izquierda de ese punto y positivo a la derecha. Así, $x - \log_a x$ disminuye a medida que $x$ se acerca a $1/\log_e a$ desde la izquierda, y luego aumenta a medida que nos alejamos de este punto hacia la derecha. Así, el valor mínimo se alcanza en $x = 1/\log_e a$ . (Aquí estoy asumiendo que $a > 1$ para que $\log_e a > 0$ el análisis del problema es un poco diferente si $a < 1$ desde entonces para $x < a < 1$ tenemos $log_a x > 1 > x,$ y la afirmación es no es cierta).

Ahora este valor es igual a $1/\log_e a + (\log_e \log_e a)/\log_e a,$ y quieres que esto sea $> 0 $ . Esto será así siempre que $a > e^{1/e}$ (como se indica en los comentarios).

Answer 2

Supongamos que $x>0$ y $\log x > x$ . Como el mapa exponencial es monotónico creciente, se deduce que $x > e^x$ . Esto contradice la conocida representación en serie para $e^x$ :

$$x\not>\sum_{k=0}^\infty \frac{x^k}{k!}=1+x+\frac{x^2}{2}+\frac{x^3}{6}+\cdots$$

También tenemos el siguiente resultado, más fuerte: ya que $e^x>1+x$ para todos $x>0$ tenemos $x > \log(1+x)$ para $x>0$ .

Editar: Parece que la pregunta se refiere a $\log_2$ y no $\log$ que requiere una prueba diferente. Por lo tanto, para que $b >1$ ¿tenemos $\log_b x <x$ para todos $x>0$ ?

La prueba anterior muestra que el conjunto de admisibles $b$ no está vacío. Como $b \to 1$ desde arriba, las curvas $\log_b x$ barrer hacia la línea $f(x)=x$ . No es difícil ver que estas funciones barren más allá de $f(x)$ por lo que existe un máximo $b$ tal que $\log_{b} x \not < x$ para todos $x>0$ . De ello se desprende que $\log_{b} x$ comparten una línea tangente para algunas $b_0$ .

Dejemos que $x_0$ denotan dicho punto de tangencia. Comparando las pendientes, debemos tener $1/(x_0\log b_0)=1$ es decir $x_0=1/\log b_0$ . Como las funciones $\log_{b_0} x$ y $x$ debe además acordar en $x_0$ calculamos $\log_{b_0}(1/\log b_0)=1/\log b_0$ Por lo tanto $\log b_0=1/e$ . Esto da un valor de $$b_0 =e^{1/e} \approx 1.44467,$$ tal que $b>b_0$ implica que $\log_b x < x$ para todos $x >0$ . En particular, $b_0<2$ para que $\log_2 x < x$ para todos $x>0$ .

Puede que haya algunos detalles escondidos bajo la alfombra, pero la idea (y la constante resultante) es ciertamente correcta.

Answer 3

Creo que he conseguido responder a esta pregunta:

La prueba es por contradicción:

Supongamos que Log X >= X para todo X > 0.

Entonces definimos que Log X es igual a Y. X debe ser <= Y, por definición.

Por la definición de logaritmos, 2^Y = X. Usando una simple sustitución, podemos decir que 2^Y <= Y, ya que X es <= Y.

Esta desigualdad sólo se cumple para Y < 0. Como X <= Y, entonces la desigualdad también se cumple sólo para X <= 0, vía silogismo. Por tanto, Log X >= X si y sólo si X <= 0, por lo que Log X < X para todo X > 0.

Answer 4

Si la proposición es verdadera, entonces $\frac{\ln x}{x} < 1$ para $x > 0$ .

Dejemos que $x = e^z$ . La condición $x > 0$ se traduce en $z \in \mathbb R$ : ninguna restricción sobre $z$ .

Entonces $\frac{\ln e^z}{e^z} = \frac{z\ln e}{e^z} = \frac{z}{e^z} < 1$ para todos $z$ .

Para los negativos $z$ Esto es cierto por la inspección. $e^z$ es positivo, por lo que $\frac{z}{e^z}$ es negativo y, por tanto, menor que $1$ .

La proposición es verdadera en $z = 0$ , donde $\frac{z}{e^z}$ . Además, $\lim_{z\to\infty}\frac{z}{e^z} = 0$ porque $e^z$ crece mucho más rápido que $z$ .

Entre estos extremos, la función alcanza un máximo, que podemos encontrar utilizando el cálculo.

$$\frac{d}{dz}\frac{z}{e^z} = 0$$

$$\rightarrow\frac{e^z - ze^z}{e^{2z}} = 0$$

$$\rightarrow e^z - ze^z = 0$$

$$\rightarrow e^z(1 - z) = 0$$

$$\rightarrow z = 1$$

En este máximo, el valor es $1/e$ que es menor que 1. Así que, de hecho, no sólo $\frac{z}{e^z} < 1$ pero en realidad $\frac{z}{e^z} \le \frac{1}{e}$ .

A partir de esto podemos trabajar hacia atrás para $\frac{\ln x}{x} < 1$ lo que demuestra que $\ln x$ < $x$ .

¿Podemos generalizar esto a otras bases, para descubrir si esto es cierto para algunas bases más pequeñas $b$ , $1 < b < e$ . La base 2 está en este rango.

Repitamos el argumento para una base generalizada $b$ empezando por la proposición $\frac{z}{b^z} < 1$ .

Aagin, esta proposición es verdadera en $z = 0$ de la misma manera, y tiene el mismo límite $0$ hasta el infinito, y algún valor máximo donde la derivada es cero:

$$\frac{d}{dz}\frac{z}{b^z} = 0$$

$$\rightarrow\frac{b^z - zb^z\ln b}{b^{2z}} = 0$$

$$\rightarrow b^z - zb^z\ln b = 0$$

$$\rightarrow b^z(1 - z\ln b) = 0$$

$$\rightarrow z = \frac{1}{\ln b}$$

En $z = \frac{1}{\ln b}$ el valor de la función es $\frac{1/{\ln b}}{e^{1/\ln b}}$ . Si esto es menor que 1, entonces la proposición que estamos tratando de demostrar es verdadera para la base $b$ :

$$\frac{1/{\ln b}}{e^{1/\ln b}} < 1$$

Elevar ambos lados a la potencia de $\ln b$ :

$$\left(\frac{1/{\ln b}}{e^{1/\ln b}}\right)^{\ln b} < 1$$

$$\frac{1/\left({\ln b}\right)^{\ln b}}{e} < 1$$

$$\frac{1}{e\left({\ln b}\right)^{\ln b}} < 1$$

$$\left({\ln b}\right)^{\ln b} > \frac{1}{e}$$

En este punto podríamos tratar ${\ln b}$ como base, y tomar el logaritmo en esa base de ambos lados pero eso no parece llevar a ninguna separación obvia de las variables.

No importa, podemos cambiar a técnicas numéricas para sondear diferentes valores de $b$ .

Es cierto para $b = 2$ y, por tanto, la proposición es válida para logaritmos de base dos. También es válida para $b = 1 + \epsilon$ para varias pequeñas $\epsilon$ . El límite parece ser 1. $\left({\ln b}\right)^{\ln b}$ parece acercarse a 1 a medida que $b$ se acerca a $1$ desde arriba, y es $1$ en $b = e$ . Entre $1$ y $e$ llega a un mínimo, pero no inferior a $1/e$ . Después de $e$ aumenta.

Así que parece que $\log_b x < x$ es válida para todas las bases $b > 1$ .