# Math Help - Proof by Induction

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 $x$, but yours is defined for all $x$...

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

3. $\log{x} < x$

$x < e^x$

$e^x - x > 0$.

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

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

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

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

$> 0$ for $x > 0$.

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

Since $e^x -x > 0$

$e^x > x$

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

$log_ek

P(k+1)

$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

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

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

If P(k) is valid, then

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

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

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

Certainly true for at least $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 ...

$log_ek

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

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

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

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

$k^2+k ?

$k(k+1) ?

For $0

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

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

$log_ek

P(k+1)

Proof

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

If P(k) is valid, then

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

now if P(k) said that

$log_ek>k$

then it would force

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

but we can still have P(k) and

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

and

$\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 $k \geq 1$, $1+\frac{1}{k} \leq 2$

so that

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

then we have that

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

is true for all $k \geq 1$