- #1

- 301

- 0

## Homework Statement

We are given the sequence r defined by: r

_{1}= 1, and r

_{n}= 1 + r

_{floor(√n) }, n≥2

We need to show by induction that r

_{n}is O (log

_{2}(log

_{2}n)).

## The Attempt at a Solution

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

[/B]

So the basic proof format is fairly simple. My issue is with the inductive step. We let for n≥3, P(n): r

_{n}≤ 4log

_{2}(log

_{2}n)). 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 r

_{n+1}= 1 + r

_{floor(√(n+1))}to 4log

_{2}(log

_{2}n+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: