1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complete Induction Proof

  1. Jan 30, 2015 #1
    1. The problem statement, all variables and given/known data
    We are given the sequence r defined by: r1 = 1, and rn = 1 + rfloor(√n)
    , n≥2
    We need to show by induction that rn is O (log2 (log2 n)).

    3. The attempt at a solution

    Definition of big oh: ∃c∈ℝ+, ∃B∈ℕ, ∀n∈ℕ, n≥B => f(n) ≤ cg(n)

    So the basic proof format is fairly simple. My issue is with the inductive step. We let for n≥3, P(n): rn ≤ 4log2(log2n)). Now this comes from the defn. of big oh and is what we have to use induction to prove. In addition, from the definition of big oh, we defined c = 4, since it seems to work.

    My issue is in the inductive step I have to show P(n+1) but have no idea how to proceed. How do I get from rn+1 = 1 + rfloor(√(n+1)) to 4log2(log2n+1) ? I'm trying to invoke the IH but don't know how to simplify either expression. Any hints would be appreciated.

    Also maybe this thread should belong to the computer science section instead.
     
    Last edited: Jan 30, 2015
  2. jcsd
  3. Jan 30, 2015 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I would suggest not assuming c=4 just yet. Leave it as c.
    What do you get when you substitute for rfloor(√(n+1)) using the IH?
     
  4. Jan 30, 2015 #3
    Ok I'll assume c is arbitrary for now. But i can't just use the IH directly on rfloor(√(n+1)) since i have to simplify it first. My issue is I have no idea how to go about simplifying it.
    And as a note: We let n∈ℕ, then the IH is P(n) or for complete induction it would be for 3≤k<n, P(k).
     
  5. Jan 30, 2015 #4
    Like haruspex suggested, assume the IH to be true:
    $$
    r_n = 1 + r_{\lfloor\sqrt{n}\rfloor} \leq 1 + c\log(\log\sqrt{n})
    $$
    Recall then that you'd like a ##c\log(\log n)## term on the RHS of the inequality.

    Edit: I did the problem using different notation, and it came out as nonsense here. Removed that part.
     
    Last edited: Jan 30, 2015
  6. Jan 30, 2015 #5
    So I'm kinda confused where did the square root come from in the expression log2(log2√n)
     
  7. Jan 31, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You want to show rn+1 <= something, call it X. So you want to show rfloor(√(n+1)) <= X. The simplification is to find some Y such that rfloor(√(n+1)) is clearly <= Y, then show Y <= X. Is the r sequence monotonic?
     
  8. Jan 31, 2015 #7
    We aren't given whether the sequence is monotonic or not. So I understand that I need to find Y. My issue is I don't know how to reduce rfloor(√(n+1)) into some Y, from which I can employ the IH.
     
  9. Jan 31, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Sorry, I asked the wrong question. I should have asked whether the log function is monotonic.
     
  10. Jan 31, 2015 #9

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Can you show that the sequence is monotonic?

    Try writing out the first part of the sequence. It increases very slowly, which is not a surprise, considering what you're asked to prove.

    For what values of n is ##\ r_{n+1}>r_n \ ## ?
     
  11. Jan 31, 2015 #10
    But lets say its monotonic, in what way does that help us ? Maybe if it was monotonically decreasing, then it would help us in the proof as follows:
    rfloor(√(n+1)) ≤ rfloor(√(n)) , and then we can invoke the inductive hypothesis. But if its increasing which it is than how does it help us ?
     
  12. Jan 31, 2015 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    As I wrote in post #8, what's useful is to think about monotonicity of the log function.
    Apply the IH to 1 + rfloor(√n). What do you get? What's an upper bound for that?
     
  13. Jan 31, 2015 #12
    Okay that makes more sense since the log function is increasing monotonically.

    Applying the induction hypothesis: 1 + rfloor(√n) ≤ clog2(log2n)., and from here we can use the monotonicity of the logarithmic function to get to clog2(log2n+1). Although, we will have to prove the monotonicity of the log function separately I guess.

    And I'm still unsure how to get from 1 + rfloor(√(n+1)) to 1 + rfloor(√n) ?
     
  14. Jan 31, 2015 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, not just 'n' inside the logs on the right. What does n represent in the IH?
     
  15. Jan 31, 2015 #14
    Just to clarify which IH are you referring to, for simple induction of for complete induction. If the latter, than n is the upper bound. This is the case we want to show is true. Not sure if that is what you mean.
     
  16. Jan 31, 2015 #15

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I mean in rn ≤ c log2(log2n)). How do you apply that to rfloor(√(n+1))?
     
  17. Feb 1, 2015 #16
    But that was my initial question ? I'm not sure how to apply it to rfloor(√(n+1)).
     
  18. Feb 1, 2015 #17

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Maybe it would help if we used two different indexes. The inductive hypothesis is, say, rk≤ c log2(log2k)). What do you have to set k to so that it applies to rfloor(√(n+1))?
     
  19. Feb 1, 2015 #18
    We would have to set k = n + 1. So then we have 1+ rfloor(√(n+1) = 1+ rfloor(√(k) but we can't conclude that its ≤ c log2(log2k))
    since our induction hypothesis only assume rn to be true.
     
  20. Feb 1, 2015 #19

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No. You need to set k to something which will make the left hand side look like rfloor(√(n+1). I'm not asking you to do anything difficult here.
     
  21. Feb 1, 2015 #20
    Oh just set it equal to k = floor(√(n+1)). Then rk is ≤ the log term by the IH.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Complete Induction Proof
  1. Proof By Induction (Replies: 2)

  2. Complete Induction (Replies: 0)

  3. Proof by induction (Replies: 1)

  4. Proof by Induction (Replies: 3)

Loading...