Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
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
up vote 5 down vote accepted

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

Added

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.

share|cite|improve this answer
    
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
1  
@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$

share|cite|improve this answer
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
1  
@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.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

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}^+$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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