# Prove that $\log(x) < x$ for $x > 0$, $x\in \mathbb{N}$.

I'm trying to prove $\log(x) < x$ for $x > 0$ by induction.

Base case: $x = 1$

$\log (1) < 1$ ---> $0 < 1$ which is certainly true.

Inductive hypothesis: Assume $x = k$ ---> $\log(k) < k$ for $k > 0$

Inductive conclusion: Prove $\log(k+1) < k+1$

I don't know what to do after this. I mean the statement itself is quite obviously true, but how do I continue with the proof?

-
I've only skimmed this one but I don't think it has any proof by induction. Still, it could help. math.stackexchange.com/questions/380963/… – 2012ssohn Apr 6 '14 at 2:38
Thanks I saw this, however I need to prove this by induction and I don't know how that could be done. – user140751 Apr 6 '14 at 2:45
@user47515 You can't prove this by induction. Not for all $x>0$. You can prove it by induction for $x\in\mathbb N$. – Jack M Apr 6 '14 at 2:57
@user47515 I added the steps for your induction that you want to use. Remember this only proves that $x > \log(x)$ for $x \in \mathbb{N} \setminus \{0\}$. – Rustyn Apr 6 '14 at 3:02
Instead of considering $\ln x<x$ consider the equivalent form $e^x>x$. Now observe that $e>2$. So $e^x>2^x$ (we can write this since $x\ge 1$). Now it is easy to prove $P(n):2^n>n$. – user 170039 Jul 14 at 14:36

I don't know why you'd use induction, (unless your domain of each function is $\mathbb{N}\setminus \{0\}$). Here is an alternative approach using calculus. If this is not helpful, I can delete this answer.

Let $g(x)= x- \log(x)$.

$g'(x) = 1 - \frac{1}{x} > 0$

for all $x >1$. So $g(x)$ is increasing on $(1,\infty)$.

At $x=1$, $g(x) = 1$, thus $x - \log(x) \ge 0$ for all $x \ge 1$.

Now for $x\in (0,1)$, $\log(x) < 0$ and $x>0$ thus $x-\log(x) > 0$.

Thus $x-\log(x) > 0$ for all $x \in (0,\infty)$. And conclude $x> \log(x)$ for all $x\in (0,\infty)$.

If you want to use induction to show that for each $x\in \mathbb{N}\setminus \{0\}$, $x>\log(x)$, use your inductive hypothesis via: $$k > \log(k) \longrightarrow \\ k+\log(1+\frac{1}{k})> \log(k)+\log(1+\frac{1}{k}) = \log(k+1) \\ k+\log(1+\frac{1}{k}) \le k + \log(2) \text{ and } \log(2) < 1 \text{ so } \\ k + \log(2) < k + 1 \text{ thus } \\ k+1 > k + \log(2) \ge k + \log(1+\frac{1}{k}) > \log(k+1)$$ Q.E.D.

-
The problem I'm trying to solve explicitly says to use induction. The calculus approach makes more sense to me though. Also don't delete your answer it could be helpful to others! – user140751 Apr 6 '14 at 2:44
@user140751 But the functions $x$, $\log x$ are usually defined over subsets of $\mathbb{R}$. Induction really only makes sense if you are talking about the natural numbers. If you prove $x > \log(x)$ for $x$ a natural number,you still haven't proved $x>\log(x)$ where $x$ is a real between two natural numbers. – Rustyn Apr 6 '14 at 2:46

Induction only works for integers. The easiest way to prove this is to note that $e^x>x$ (The power series for $e^x$ is only positive terms and one of them is $x$), and then let $x=\ln{y}$.

For a proof by induction, factoring $k$ out, yields $\ln{(k+1)}=\ln{k}+\ln{(1+\frac{1}{k})}<k+\ln{(1+\frac{1}{k})}<k+1$ since $\log{2}<1$

-
$\log(ab) \neq \log(a)\cdot \log(b)$. Consider $a = e$ and $b = 1$. Then $\log(ab) = \log(e) = 1$, but $\log(a)\cdot \log(b) = 1\cdot 0 = 0$. You are mistaking the correct identity: $\log(ab) = \log(a)\cdot \log(b)$. – Chris K Apr 6 '14 at 2:50
@ChrisK I think you mean $\log(ab) = \log(a) + \log(b)$ for the "correct identity." ;) – apnorton Apr 6 '14 at 2:53
Thank you! Brain fart. I wrote down the mistake. Yes, indeed. – Chris K Apr 6 '14 at 2:55
That would be the case! I did finish the inductive proof now. – Stella Biderman Apr 6 '14 at 2:56

(I) Let $x\in \mathbb R, x>0$. Maclaurin series for $e^x$: $e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+...$,
So $e^x-x=1+\frac{x^2}{2!}+\frac{x^3}{3!}+...>0$ or $e^x>x$ or $x>log(x)$. When $x\in \mathbb N^+\subset\mathbb R$ , the statement is still true. This completes the proof.

(II) If $x\in \mathbb R$
Let $g(x)=x-log(x)$.
Since $g(1)=1$,and $g'(x)=1-\frac1x>0$ when $x>1$,
on the interval $(1, \infty)$, $g(x)>1>0$,
or $x>log(x)$.
On the interval $(0,1), x>0, log(x)<0$, so $x>log(x)$,
when $x=1$, then $log(x)=0<1=x$, so $x>log(x)$. Since $x\in \mathbb N^+ \subset \mathbb R$ , The statement is still true for $x>0, x\in \mathbb N$.
This completes the proof.

(III)If x $\in \mathbb R$
Since $e^t|_{t=0}=1$, and $e^t$ is monotonically increasing in interval $(0,\infty)$, Thus $e^t>1$ is always true when t>0.
so $\int^x_0e^tdt> \int^x_0dt$, for $x>0$ or $1+\int^x_0e^tdt> \int^x_0dt$ or $e^x>x$ when $x>0$
or $e^x>x>0$,
or $1>\frac x{e^x}>0$
or $log (\frac x{e^x})<0$,
or $log(x)-log(e^x)<0$
or $log(x)<log(e^x)$ or $log(x)<x$ when $x>0$.
Since $x\in \mathbb N^+ \subset \mathbb R$ , The statement is still true. This completes the proof.

-

This can indeed be proven with induction, but there's a few steps (we have to use induction a few times). Besides my proof is only for $x>1$ so we'll conclude that the inequality holds for $x=1$ right away (since $\log(1)=0$ and $0<1$).

Lemma 1: For $a\ge2$ we have $2a\ge2+a$

Proof: $2a = a+a$ and since $2\ge2$ we have $a+a\ge a+2$. We could have used induction here if we wanted to complicate it.

Lemma 2: For $a,b\ge 2$ we have $ab\ge a+b$

Proof: From lemma 1 we know this to be true for $b=2$, and now suppose it's true for some $b\ge2$ then we have $a(b+1) = ab + a \ge a+b+a \ge a+(b+1)$. By induction it follows that $ab \ge a+b$ for all $b\ge 2$.

Lemma 3: If $n\ge1$ then $\log(2^n) < 2^{n-1}$

Proof: For $n=1$ this is true because $\log2 < 1 = 2^{1-0}$. Now suppose it's true for some $n$ then $\log 2^{n+1} = \log 2^n + \log 2$. By lemma 2 this means $\log 2^{n+1}\le \log 2^n \log 2 < 2^{n-1}\log 2$, and since $\log 2<1<2$ we have $\log 2^{n+1} < 2^{n-1}2 = 2^{(n+1)-1}$. By induction the claim follows.

Lemma 4: If $a\ge1$ there's an $n$ such that $2^{n-1} \le a < 2^n$.

Proof: For $a=1$ this is obvious since $n=1$ is such an $n$ since $2^{1-1}=1 \le a < 2^1 = 2$. Now suppose it's true for some $a$ (and the solution $n$), and assume it weren't true for $a+1$. Obviously we have that $2^{n-1}\le a <2^n$ isn't true. But we know that if $2^{n-1}\le a$ we certainly have that $2^{n-1}<a+1$ so it's the second inequality that must fail. So we have $(a+1) \ge 2^n$, but since at the same time we have $a < 2^n$ we can conclude that $a+1 = 2^n$ - now it follows that $2^n \le (a+1) < 2^{n+1}$ which contradicts the assumtion and by RAA we conclude that it's true for $(a+1)$ as well

Proposition: If $x>1$ then $\log(x) < x$.

Proof: Since $x>1$ we have by Lemma 4 an $n$ such that $2^{n-1}\le x<2^n$. Now $\log x < \log 2^n$ and by lemma 3 it follows that $\log x < \log 2^n < 2^{n-1} \le x$.

If you want to prove the statement for arbitrary real numbers however you can still do this with induction perhaps. What I'd try is to show that the inequality is true with marigin - that is to prove that $\log n<n-1$ for $n\ge 1$ you can use this to estimate $\log x\le\log \lceil x\rceil<\lceil x\rceil-1 \le x$ (where $\lceil x\rceil$ is the smallest integer no less than $x$).

-

$\log''(x) = -x^{-2}$ is negative, so $\log$ is concave, so it is bounded above by all of its tangents: $$\log(x) \leq x-1 < x.$$

-

Here is a proof, using induction, for all $x\in\mathbb{R}^+$, not just $x\in\mathbb{N}$.

Recall that the graph of an inverse function is obtained by reflecting across the line $y=x$. Consequently we have

$$\ln x\lt x \text{ for all }x\in\mathbb{R}^+\iff x\lt e^x\text{ for all }x\in\mathbb{R}$$

so it suffices the prove the inequality on the right.

Now $0\lt e^x$ for all $x$, so $x\lt e^x$ for $x\lt0$ is clear. (This is equivalent to noting that $\ln x\lt0\lt x$ for $0\lt x\lt 1$.) For $0\le x$, note that $2\lt e$ implies $2^x\le e^x$, so it suffices to show $x\lt2^x$ for all $x\ge0$. We'll do this by induction on the following assertion:

$$\text{For all }n\in\mathbb{N},\quad n\le x\lt n+1\implies x\lt2^x$$

For the base case, if $0\le x\lt1$, then $x\lt1=2^0\lt2^x$, using the increasing nature of the exponential function. If we now make the inductive assumption that the statement is true for $n$, then

\begin{align} n+1\le x\lt n+2&\implies n\le x-1\lt n+1\\ &\implies x-1\lt2^{x-1}\\ &\implies x\lt2^{x-1}+1\\ &\implies x\lt2^{x-1}+2^n\quad(\text{since }n\ge0)\\ &\implies x\lt2^{x-1}+2^{x-1}\\ &\implies x\lt 2^x\\ \end{align}

Since every non-negative real number $x$ lies between two consecutive non-negative integers, this proves $x\lt2^x\le e^x$ for all $x\ge0$. Putting this together with the earlier observation that $x\lt e^x$ for $x\lt0$ is clear, we conclude that $x\lt e^x$ for all $x\in\mathbb{R}$, and therefore, by the inverse-function equivalence, $\ln x\lt x$ for all $x\in\mathbb{R}^+$.

-