I'm working through Data Structures and Algorithm Analysis in C++, 2nd Ed, and problem 1.7 asks us to prove that $\log X < X$ for all $X > 0$.
However, unless I'm missing something, this can't actually be proven. The spirit of the problem only holds true if you define several extra qualifiers, because it's relatively easy to provide counter examples.
First, it says that $\log_{a} X < X$ for all $X > 0$, in essence.
But if $a = -1$, then $(-1)^{2} = 1$. Therefore $\log_{-1} 1 = 2$. Thus, we must assume
$a$ is positive.
if $a$ is $< 1$, then $a^2 < 1$. Therefore we must assume that $a \geq 1$.
Now, the book says that unless stated otherwise, it's generally speaking about base 2 for logarithms, which are vital in computer science.
However, even then – if $a$ is two and $X$ is $\frac{1}{16}$, then $\log_{a} X$ is $-4$. (Similarly for base 10, try taking the log of $\frac{1}{10}$ on your calculator: It's $-1$.) Thus we must assume that $X \geq 1$.
…Unless I'm horribly missing something here. The problem seems quite different if we have to prove it for $X \geq 1$.
But even then, I need some help solving the problem. I've tried manipulating the equation as many ways as I could think of but I'm not cracking it.
Best Answer
One way to approach this question is to consider the minimum of $x - \log_a x$ on the interval $(0,\infty)$. For this we can compute the derivative, which is $1 - 1/(\log_e a )\cdot x$. Thus the derivative is zero at a single point, namely $x = 1/\log_e a,$ and is negative to the left of that point and positive to the right. Thus $x - \log_a x$ decreases as $x$ approaches $1/\log_e a$ from the left, and then increases as we move away from this point to the right. Thus the minimum value is achieved at $x = 1/\log_e a$. (Here I'm assuming that $a > 1$, so that $\log_e a > 0$; the analysis of the problem is a little different if $a < 1$, since then for $x < a < 1$, we have $log_a x > 1 > x,$ and the statement is not true.)
Now this value is equal to $1/\log_e a + (\log_e \log_e a)/\log_e a,$ and you want this to be $> 0 $. This will be true provided $a > e^{1/e}$ (as noted in the comments).