1. ## Proof by Induction

Prove inductively that log(x) < x for x>0

Base: log1=0<1
Assume log(k)<k
Show log(k+1)<k+1
log(k+1) = log(k) + log(1/k + 1)
substitute k for log(k)
Show k + log(1/k + 1) < k + 1
log(1/k + 1) <1
log (1/k + 1) = log ((k+1)/k) = log(k+1) - log k
log (k+1) -log(k) < 1
log (k+1) < 1 + log (k)

Now what? I think I'm taking the wrong approach, but I can't see another one...

2. I don't think you can use induction here, since induction only works for integer values of $\displaystyle x$, but yours is defined for all $\displaystyle x$...

Also, you're asked to prove it for $\displaystyle x > 0$, but you can't evaluate $\displaystyle \log{0}$, and if you start at $\displaystyle \log{1}$ that doesn't tell you about anything between $\displaystyle 0$ and $\displaystyle 1$.

3. $\displaystyle \log{x} < x$

$\displaystyle x < e^x$

$\displaystyle e^x - x > 0$.

This is obviously true for $\displaystyle x = 0$, because $\displaystyle e^0 - 0 = 1 - 0 = 1$...

Now we just need to show that this function is increasing...

$\displaystyle f(x) = e^x - x$

$\displaystyle f'(x) = e^x - 1$

$\displaystyle > 0$ for $\displaystyle x > 0$.

Since $\displaystyle e^x - x > 0$ for $\displaystyle x = 0$ and is an increasing function, that means $\displaystyle e^x - x > 0$ for all $\displaystyle x$.

Since $\displaystyle e^x -x > 0$

$\displaystyle e^x > x$

$\displaystyle x > \log{x}$.

Q.E.D.

4. I'm told explicitly to use induction... can you see a way if we were only considering integers?

5. Originally Posted by veronicak5678
Prove inductively that log(x) < x for x>0

Base: log1=0<1
Assume log(k)<k
Show log(k+1)<k+1
log(k+1) = log(k) + log(1/k + 1)
substitute k for log(k)
Show k + log(1/k + 1) < k + 1
log(1/k + 1) <1
log (1/k + 1) = log ((k+1)/k) = fine to here log(k+1) - log k
log (k+1) -log(k) < 1
log (k+1) < 1 + log (k)

Now what? I think I'm taking the wrong approach, but I can't see another one...
For the natural logarithm...

P(k)

$\displaystyle log_ek<k$

P(k+1)

$\displaystyle log_e(k+1)<(k+1)$

Try to show that if P(k) really is valid, then it causes P(k+1) to also be valid.

Proof

$\displaystyle log_e\left(k+1\right)<(k+1)$ ?

$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)+log_ek<(k+1)$ ?

If P(k) is valid, then

$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)<1$ ?

$\displaystyle \displaystyle\ log_e\left(\frac{k+1}{k}\right)<1$ ?

$\displaystyle \displaystyle\frac{k+1}{k}<e$ ?

Certainly true for at least $\displaystyle k\ge\ 1$

6. Shouldn't it be true for k > 0 ?

7. Originally Posted by veronicak5678
Shouldn't it be true for k > 0 ?
Yes, though that means a base case of 0 and continuous values of x, rather than discrete integers.
I thought you were obtaining a proof for natural numbers.

If you write ...

$\displaystyle log_ek<k$

$\displaystyle log_e(k+1)<(k+1)$ ?

$\displaystyle \displaystyle\ log_e\left(\frac{k^2+k}{k}\right)<(k+1)$ ?

$\displaystyle log_e\left(k^2+k\right)-log_ek<(k+1)$ ?

$\displaystyle log_e\left(k^2+k\right)<2k+1$ ?

$\displaystyle k^2+k<e^{2k+1}$ ?

$\displaystyle k(k+1)<e^{2k}e$ ?

For $\displaystyle 0<k<1,\;\;\;k(k+1)<2$

while $\displaystyle e^{2k}\ge\ 1\Rightarrow\ k(k+1)<e$ for $\displaystyle 0<k<1$

then you have a totally invalid solution since the domain is digitized k, k+1, k+2, k+3..... and not continuous.

I will try to come up with a proof valid for all x>0.

8. Originally Posted by veronicak5678
Shouldn't it be true for k > 0 ?
The fact that you are using induction means you have only proved it for integers. If k is an integer, k> 0 means $\displaystyle k\ge 1$!

9. I see. I wasn't thinking last night (this morning). Thanks for all your help!

10. Originally Posted by Archie Meade
For the natural logarithm...

P(k)

$\displaystyle log_ek<k$

P(k+1)

Proof

$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)+log_ek<(k+1)$ ?

If P(k) is valid, then

$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)<1$ ?
if P(k) is valid this does not mean that
$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)<1$

now if P(k) said that

$\displaystyle log_ek>k$

then it would force

$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)<1$

but we can still have P(k) and

$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)>1$

and

$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)+log_ek<(k+1)$

to all be true.

How i would tackle the problem is to do what you've done till

"If P(k) is valid"

and then for all $\displaystyle k \geq 1$, $\displaystyle 1+\frac{1}{k} \leq 2$

so that

$\displaystyle log_e(1+\frac{1}{k}) \leq log_e(2) \leq 1$ (of course since $\displaystyle log_e(x)$ is an increasing function)

then we have that

$\displaystyle \displaystyle\ log_e\left(1+\frac{1}{k}\right)+log_ek<(k+1)$ (log(k) is strictly less than k)

is true for all $\displaystyle k \geq 1$