We are given the sequence r defined by: r1 = 1, and rn = 1 + rfloor(√n)
We need to show by induction that rn is O (log2 (log2 n)).
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.