Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inductive hypothesis

  1. Aug 14, 2011 #1

    I would like to ask a question that is related to the inductive hypothesis with Asymptotic notation.

    lg(n) = O(n)
    Intuitively: lg(n) < n for all n ≥ 1.
    Need a proof. Well
    lg(n) < n ⇐⇒ n < 2n , for all n > 0.
    Use induction on n to prove rhs.
     Base case n = 1 is clearly true.
     For induction step assume claim holds for n. Then
    2n+1= 2 · 2n> 2n, by induction hypothesis.

    To complete the proof just need to show that 2n ≥ n + 1.

    2n ≥ n + 1 ⇐⇒ n ≥ 1,
    and we have finished.
    So we take c = 1 and n0 = 1

    I don't know how we got this answer in these two lines:
    1)2n+1= 2 · 2n> 2n
    2)2n ≥ n + 1 ⇐⇒ n ≥ 1,

    If you can explain this example for me, I would really appreciate that.

  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?