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
    Hello,

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

    Example:
    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.

    Now
    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.

    thxx
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted



Similar Discussions: Inductive hypothesis
  1. Induction Hypothesis: (Replies: 1)

  2. Hypothesis test (Replies: 5)

  3. Hypothesis tests (Replies: 3)

  4. Hypothesis testing (Replies: 0)

  5. Hypothesis Testing (Replies: 3)

Loading...