Results 1 to 10 of 10

Thread: Proof by Induction

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    225

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    12,880
    Thanks
    1946
    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$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    12,880
    Thanks
    1946
    $\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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2008
    Posts
    225
    I'm told explicitly to use induction... can you see a way if we were only considering integers?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    Quote Originally Posted by veronicak5678 View Post
    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$
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2008
    Posts
    225
    Shouldn't it be true for k > 0 ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    Quote Originally Posted by veronicak5678 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,793
    Thanks
    3035
    Quote Originally Posted by veronicak5678 View Post
    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$!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Aug 2008
    Posts
    225
    I see. I wasn't thinking last night (this morning). Thanks for all your help!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jul 2009
    Posts
    193
    Thanks
    5
    Quote Originally Posted by Archie Meade View Post
    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$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction that 4| 5^n - 1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 10:23 AM
  2. proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 17th 2010, 07:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: Nov 1st 2008, 04:32 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum