Thursday, January 24, 2019

induction - Prove that $log(x) 0$, $xin 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?


Answer



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) > 0$ for all $x \ge 1$ (use continuity and the known value at $x = 1$ with what has just been shown about the monotony of $g$).

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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...