Results 1 to 10 of 10

Math Help - 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
    11,404
    Thanks
    1293
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,404
    Thanks
    1293
    \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.
    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
    1
    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)

    log_ek<k


    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}<e ?

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

    log_ek<k

    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<e^{2k+1} ?

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


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

    while e^{2k}\ge\ 1\Rightarrow\ k(k+1)<e for 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
    15,383
    Thanks
    1318
    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 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
    192
    Thanks
    4
    Quote Originally Posted by Archie Meade View Post
    For the natural logarithm...

    P(k)

    log_ek<k


    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
    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: February 17th 2010, 07:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 1st 2008, 04:32 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum