8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome and remember! Use of $\LaTeX$ syntax is highly recommended. $\endgroup$ – Sangchul Lee May 4 '13 at 8:16
  • 6
    $\begingroup$ Nobody cares for logarithms with negative bases. In fact, they are $2$ or $e$ (Eulerian number) most of the time. Your counterexample for $2$ is not a counterexample, the inequality holds in that case, right? $\endgroup$ – Martin Brandenburg May 4 '13 at 8:17
  • 3
    $\begingroup$ You can prove that whenever $a > e^{1/e}$, then $\log_{a} X < X$ for all $X > 0$. Note that your alleged counterexample is in fact not a counterexample. $\endgroup$ – Sangchul Lee May 4 '13 at 8:22
  • 1
    $\begingroup$ @MartinBrandenburg And 10. $\endgroup$ – Did May 4 '13 at 8:25
  • $\begingroup$ ah, yes, I conflated the value of x with logaX $\endgroup$ – Andy Isbell May 4 '13 at 9:27
10
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

I believe I managed to answer this question:

Proof is by contradiction:

Let us assume that Log X >= X for all X > 0.

Then we define Log X to be equal to Y. X must be <= Y, by definition.

By the definition of logarithms, 2^Y = X. Using simple substitution, we can say that 2^Y <= Y, since X is <= Y.

This inequality only holds true for Y < 0. Since X <= Y, then the inequality also holds true only for X <= 0, via syllogism. Thus Log X >= X if and only if X <= 0, thus Log X < X for all X > 0.

$\endgroup$
  • $\begingroup$ Contradiction requires only "Log X >= X for some X > 0". :) $\endgroup$ – Kaz May 17 '13 at 14:20
  • $\begingroup$ If $\log x \geq x$ for some $x$, indeed that must mean that $2^y \leq y$. But if we can just jump to the conclusion that this is nonsense by definition, why don't we just do that for $\log x \geq x$? $\endgroup$ – Kaz May 17 '13 at 14:25
  • $\begingroup$ @Kaz I'm not sure what you're saying--I think we needed the Y to reverse the logarithm, since just saying that it's nonsense by definition for log x >= x doesn't show how? $\endgroup$ – Andy Isbell May 18 '13 at 6:22
  • $\begingroup$ Your argument seems to be that if we just reverse the logarithm into exponentiation, the answer is then obvious. We take the proposition $\log x < x$ and turn it into $2^y > y$ and Q.E.D. Well then, why isn't it just obvious that $\log x < x$. Why don't we have to prove that $2^y > y$? $\endgroup$ – Kaz May 18 '13 at 6:29
  • $\begingroup$ @Kaz Oh, I see what you're saying--We can see easily that $2^y <= y$ doesn't hold true for positive or zero $y$, because if y is 0, then $2^y$ is 1, and then if we raise it to any higher power, $2^y$ grows at a faster rate than y. $\endgroup$ – Andy Isbell May 18 '13 at 18:42
0
$\begingroup$

Suppose that $x>0$ and $\log x > x$. Because the exponential map is monotonic increasing, it follows that $x > e^x$. This contradicts the well-known series representation for $e^x$:

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

We also have the following, stronger result: since $e^x>1+x$ for all $x>0$, we have $x > \log(1+x)$ for $x>0$.

Edit: It appears that the question concerns $\log_2$ and not $\log$, which requires a different proof. Thus, for which $b >1$ do we have $\log_b x <x$ for all $x>0$?

The proof above shows that the set of admissible $b$ is non-empty. As $b \to 1$ from above, the curves $\log_b x$ sweep down towards the line $f(x)=x$. It's not hard to see that these functions sweep past $f(x)$, hence there exists a maximal $b$ such that $\log_{b} x \not < x$ for all $x>0$. It follows that $\log_{b} x$ share a tangent line for some unique $b_0$.

Let $x_0$ denote such a point of tangency. Comparing slopes, we must have $1/(x_0\log b_0)=1$, i.e $x_0=1/\log b_0$. As the functions $\log_{b_0} x$ and $x$ must moreover agree at $x_0$, we compute $\log_{b_0}(1/\log b_0)=1/\log b_0$, hence $\log b_0=1/e$. This gives a value of $$b_0 =e^{1/e} \approx 1.44467,$$ such that $b>b_0$ implies that $\log_b x < x$ for all $x >0$. In particular, $b_0<2$, so that $\log_2 x < x$ for all $x>0$.

There may be some details swept under the rug, but the idea (and resulting constant) is certainly correct.

$\endgroup$
  • $\begingroup$ Dear A Walker, The OP was also (perhaps principally) interested in the case of $\log$ to the base $2$, rather than natural log. Regards, $\endgroup$ – Matt E May 17 '13 at 5:08
  • $\begingroup$ @MattE Edited and expanded! $\endgroup$ – awwalker May 17 '13 at 5:47
0
$\begingroup$

If the proposition is true then $\frac{\ln x}{x} < 1$ for $x > 0$.

Let $x = e^z$. The condition $x > 0$ translates to $z \in \mathbb R$: no restriction on $z$.

Then $\frac{\ln e^z}{e^z} = \frac{z\ln e}{e^z} = \frac{z}{e^z} < 1$, for all $z$.

For the negative $z$, this is true by inspection. $e^z$ is positive, and so $\frac{z}{e^z}$ is negative and thus less than $1$.

The proposition is true at $z = 0$, where $\frac{z}{e^z}$. Furthermore, $\lim_{z\to\infty}\frac{z}{e^z} = 0$ because $e^z$ grows much faster than $z$.

In between these extremes, the function reaches a maximum, which we can find using calculus.

$$\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$$

At this maximum, the value is $1/e$ which is less than 1. So in fact not only $\frac{z}{e^z} < 1$ but in fact $\frac{z}{e^z} \le \frac{1}{e}$.

From this we can work backwards to $\frac{\ln x}{x} < 1$, which shows that $\ln x$ < $x$.

Can we generalize this to other bases, to discover whether this is true for some smaller bases $b$, $1 < b < e$. Base 2 is in this range.

Let's repeat the argument for a generalized base $b$, starting with the proposition $\frac{z}{b^z} < 1$.

Aagin, this proposition is true at $z = 0$ in the same way, and has the same limit $0$ out to infinity, and some maximum value where the derivative is zero:

$$\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}$$

At $z = \frac{1}{\ln b}$, the function's value is $\frac{1/{\ln b}}{e^{1/\ln b}}$. As long as this is less than 1, then the proposition we are trying to prove is true for base $b$:

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

Raise both sides to the power of $\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}$$

At this point we could treat ${\ln b}$ as a base, and take the log in that base of both sides but that doesn't seem to lead to any obvious separation of variables.

Never mind, we can switch to numeric techniques for probing different values of $b$.

It is true for $b = 2$, and hence the proposition holds for base two logarithms. It also holds for $b = 1 + \epsilon$ for various small $\epsilon$. The limit appears to be 1. $\left({\ln b}\right)^{\ln b}$ appears to approach 1 as $b$ approaches $1$ from above, and it is $1$ at $b = e$. Between $1$ and $e$ it hits a minimum, but not lower than $1/e$. After $e$ it increases.

So it look like $\log_b x < x$ holds for all bases $b > 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.