Can Sequence r_n Be Bounded by O(log2(log2 n))?

[NATURE.M]

Homework Statement

We are given the sequence r defined by: r₁ = 1, and r_n = 1 + r_floor(√n)
, n≥2
We need to show by induction that r_n is O (log₂ (log₂ 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₂(log₂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₂(log₂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.

 

[haruspex]

I would suggest not assuming c=4 just yet. Leave it as c.
What do you get when you substitute for r_{floor(√(n+1))} using the IH?

 

[NATURE.M]

I would suggest not assuming c=4 just yet. Leave it as c.
What do you get when you substitute for r_{floor(√(n+1))} using the IH?

Ok I'll assume c is arbitrary for now. But i can't just use the IH directly on r_{floor(√(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).

 

[milesyoung]

Ok I'll assume c is arbitrary for now. But i can't just use the IH directly on r_{floor(√(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).

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.

 

[NATURE.M]

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.

So I'm kinda confused where did the square root come from in the expression log₂(log₂√n)

 

[haruspex]

But i can't just use the IH directly on r_{floor(√(n+1))} .

You want to show r_n+1 <= something, call it X. So you want to show r_{floor(√(n+1))} <= X. The simplification is to find some Y such that r_{floor(√(n+1))} is clearly <= Y, then show Y <= X. Is the r sequence monotonic?

 

[NATURE.M]

You want to show r_n+1 <= something, call it X. So you want to show r_{floor(√(n+1))} <= X. The simplification is to find some Y such that r_{floor(√(n+1))} is clearly <= Y, then show Y <= X. Is the r sequence monotonic?

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 r_{floor(√(n+1))} into some Y, from which I can employ the IH.

 

[haruspex]

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 r_{floor(√(n+1))} into some Y, from which I can employ the IH.

Sorry, I asked the wrong question. I should have asked whether the log function is monotonic.

 

[SammyS]

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 r_{floor(√(n+1))} into some Y, from which I can employ the IH.

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 \$ ?

 

[NATURE.M]

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 \$ ?

But let's 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:
r_{floor(√(n+1))} ≤ r_{floor(√(n))} , and then we can invoke the inductive hypothesis. But if its increasing which it is than how does it help us ?

 

[haruspex]

But let's say its monotonic, in what way does that help us ?

As I wrote in post #8, what's useful is to think about monotonicity of the log function.
Apply the IH to 1 + r_floor(√n). What do you get? What's an upper bound for that?

 

[NATURE.M]

As I wrote in post #8, what's useful is to think about monotonicity of the log function.
Apply the IH to 1 + r_floor(√n). What do you get? What's an upper bound for that?

Okay that makes more sense since the log function is increasing monotonically.

Applying the induction hypothesis: 1 + r_floor(√n) ≤ clog₂(log₂n)., and from here we can use the monotonicity of the logarithmic function to get to clog₂(log₂n+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 + r_{floor(√(n+1))} to 1 + r_floor(√n) ?

 

[haruspex]

Applying the induction hypothesis: 1 + r_floor(√n) ≤ clog₂(log₂n)

No, not just 'n' inside the logs on the right. What does n represent in the IH?

 

[NATURE.M]

No, not just 'n' inside the logs on the right. What does n represent in the IH?

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.

 

[haruspex]

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.

I mean in r_n ≤ c log₂(log₂n)). How do you apply that to r_{floor(√(n+1))}?

 

[NATURE.M]

I mean in r_n ≤ c log₂(log₂n)). How do you apply that to r_{floor(√(n+1))}?

But that was my initial question ? I'm not sure how to apply it to r_{floor(√(n+1))}.

 

[haruspex]

But that was my initial question ? I'm not sure how to apply it to r_{floor(√(n+1))}.

Maybe it would help if we used two different indexes. The inductive hypothesis is, say, r_k≤ c log₂(log₂k)). What do you have to set k to so that it applies to r_{floor(√(n+1))}?

 

[NATURE.M]

Maybe it would help if we used two different indexes. The inductive hypothesis is, say, r_k≤ c log₂(log₂k)). What do you have to set k to so that it applies to r_{floor(√(n+1))}?

We would have to set k = n + 1. So then we have 1+ r_{floor(√(n+1)} = 1+ r_floor(√(k) but we can't conclude that its ≤ c log₂(log₂k))
since our induction hypothesis only assume r_n to be true.

 

[haruspex]

We would have to set k = n + 1.

No. You need to set k to something which will make the left hand side look like r_{floor(√(n+1)}. I'm not asking you to do anything difficult here.

 

[NATURE.M]

No. You need to set k to something which will make the left hand side look like r_{floor(√(n+1)}. I'm not asking you to do anything difficult here.

Oh just set it equal to k = floor(√(n+1)). Then r_k is ≤ the log term by the IH.

 

[haruspex]

Oh just set it equal to k = floor(√(n+1)).

Right. What inequality does the IH give you? Can you see how to get rid of the floor function by exploiting monotonicity of log?

 

[NATURE.M]

So here is my logic (by complete induction)
Induction Hypothesis: r_k ≡ 1 + r_{floor(√(k))} ≤ clog₂(log₂k) for 3≤k<n.
Then, r_n = 1+ r _{floor(√(n))}. By the IH, we know r_{floor(√(n))} ≤ clog₂(log₂floor(√(n))) since floor(√(n)) < n.
So then we have 1+ r _{floor(√(n))} ≤ 1 + clog₂(log₂floor(√(n))). And the log function is increasing, so 1 + clog₂(log₂floor(√(n))) ≤ 1 + clog₂(log₂n).

So I think the above should be right for the most part, I'm a bit uncertain what to do with the 1 however.

 

[haruspex]

since floor(√(n)) < n

No, you've thrown away too much. You're only trying to get rid of the floor function.

 

[NATURE.M]

No, you've thrown away too much. You're only trying to get rid of the floor function.

Isn't that what I did ? I got rid of the r_floor(√n) function, since r_floor(√n) = 1 + r_{floor(√(floor(√n))} ≤ clog₂(log₂floor(√(n))) by IH.

As an aside, thanks for being so patient.

 

[haruspex]

In doing this:

1 + c log₂(log₂floor(√(n))) ≤ 1 + c log₂(log₂n).

you've thrown away the √ as well as the floor. Only get rid of the floor.

 

[NATURE.M]

In doing this:

you've thrown away the √ as well as the floor. Only get rid of the floor.

Oh I figured it out, cause then you use that to break the log term and to cancel out the + 1 term.

And just two last questions then. Should i just leave c as is for the entire proof, as an arbitrary positive real ?
And since I'm using complete induction in my IH, I said P(k) for 2 ≤ k < n. Now is it true that floor(√(n)) < √n only if n > 1. So its fair if I prove for ≥2.

 

[haruspex]

Should i just leave c as is for the entire proof, as an arbitrary positive real ?

It isn't arbitrary. You should find it has to be at least some value for the result to work. Please post your working from where it left off.

Now is it true that floor(√(n)) < √n only if n > 1

Putting n = x², x > 0, (and correcting from '<' to '<=') you are asking whether floor(x) <= x only if x > 1. Is it?

 

[NATURE.M]

It isn't arbitrary. You should find it has to be at least some value for the result to work. Please post your working from where it left off.

Putting n = x², x > 0, (and correcting from '<' to '<=') you are asking whether floor(x) <= x only if x > 1. Is it?

Okay, so 1+ r floor(√(n)) ≤ 1 + clog₂(log₂floor(√(n))) ≤ 1 + clog₂(log₂(√(n))) = 1 + clog₂(1/2)(log₂(n))
= 1 + clog₂1/2 + clog₂(log₂(n)) = clog₂(log₂(n)), as desired.

Now I'm not entirely sure how to solve for c.

And well floor(0) <= 0, so no. However, since the sequence is only defined for n>=1 that case wouldn't be important. The case where n = 1, we can prove as a separate case (or directly) since the sequence is defined differently. However, this would require us knowing what c is. And for n>=2 we proceed as above.

 

[haruspex]

1 + c log21/2 + c log2(log2(n)) = c log2(log2(n)),

There's a mistake there. You have effectively assumed a value for c.

 

[NATURE.M]

There's a mistake there. You have effectively assumed a value for c.

Oops I missed that. In that case, can't we just let c = 1, at the beginning of the proof since the definition of big oh asks for you to choose a c. (∃c∈ℝ+).

 

[haruspex]

Oops I missed that. In that case, can't we just let c = 1, at the beginning of the proof since the definition of big oh asks for you to choose a c. (∃c∈ℝ+).

Sure. The choice for c is 1 or greater. Since you'd generally look for the tightest bound, choose 1.

 

[NATURE.M]

Sure. The choice for c is 1 or greater. Since you'd generally look for the tightest bound, choose 1.

Ok. And also just realized that n has to be ≥3 otherwise the proof fails. Namely, in the definition of big oh our choice of B should be 3. Since n = 1 is undefined for the double log term and n=2 doesn't satisfy the predicate with c = 1.

 

[haruspex]

Ok. And also just realized that n has to be ≥3 otherwise the proof fails. Namely, in the definition of big oh our choice of B should be 3. Since n = 1 is undefined for the double log term and n=2 doesn't satisfy the predicate with c = 1.

OK.
All done?

 

[NATURE.M]

OK.
All done?

Yeah I believe that is it. I can't thank you enough for your efforts and being patient with me throughout.

 

[haruspex]

Yeah I believe that is it. I can't thank you enough for your efforts and being patient with me throughout.

A pleasure.

 

[NATURE.M]

A pleasure.

So it turns out when I was writing the proof, I stumbled upon a little issue. Basically, in order to be able to use the IH on r_floor(√n) we require 3 ≤floor(√n) < n which is just not the case. Like take n = 3, then floor(√3) < 3. Even if you try to lower bound floor(√n) by 0 or 1 it doesn't work since then the log term in the predicate becomes undefined. In other words, P(n) just isn't true for n = 0, 1. This is rather unfortunate. I'm not really sure how to get around this ?

 

[milesyoung]

So it turns out when I was writing the proof, I stumbled upon a little issue. Basically, in order to be able to use the IH on r_floor(√n) we require 3 ≤floor(√n) < n which is just not the case. Like take n = 3, then floor(√3) < 3. Even if you try to lower bound floor(√n) by 0 or 1 it doesn't work since then the log term in the predicate becomes undefined. In other words, P(n) just isn't true for n = 0, 1. This is rather unfortunate. I'm not really sure how to get around this ?

You could change your base step to something like: P(n) is true for 3 ≤ n ≤ 8.

 

[NATURE.M]

You could change your base step to something like: P(n) is true for 3 ≤ n ≤ 8.

Okay that makes sense. So if i understand correctly, I can prove each individual case from let's say 3≤n≤8. Then proceed with complete induction from 8≤k<n. Would that make sense ? Because then when I do the proof, I wouldn't by just invoking the IH, I would also have to specify the truth of the base cases.

 

[milesyoung]

Okay that makes sense. So if i understand correctly, I can prove each individual case from let's say 3≤n≤8. Then proceed with complete induction from 8≤k<n. Would that make sense ? Because then when I do the proof, I wouldn't by just invoking the IH, I would also have to specify the truth of the base cases.

No, it'll be a problem if you change your IH. You could instead formulate it as:

Base step: Show that P(n) is true for 3 ≤ n < 9.
Induction hypothesis: P(k) is true for 3 ≤ k < n.
Induction step: Assume IH holds, and show that P(n) is true for n ≥ 9.

 

[haruspex]

No, it'll be a problem if you change your IH.

Would it necessarily? Seems to me it could be generalised to r_n <= A + B l₂ l₂ n. With the same algebra as before, the A's cancel out and again produce B>=1.
Yes, the base of the induction needs to be broadened. If we make the base N₀ <= n < N₁, we need N₁ >= N₀². As you say, keeping N₀=3 means means 3 to 8 have to be demonstrated separately to satisfy the IH, but consider N₀=2. We need r₂ = 2 <= A + B l₂ l₂ 2 = A.

 

[NATURE.M]

But a new issue i just noticed that none of the base cases satisfy if we take c = 1. Like r₃ = 2, and r

Should i choose c = 4 instead ?

 

[haruspex]

But a new issue i just noticed that none of the base cases satisfy if we take c = 1. Like r₃ = 2, and r

Should i choose c = 4 instead ?

Did you see my post #40?

 

[milesyoung]

Would it necessarily? Seems to me it could be generalised to r_n <= A + B l₂ l₂ n. With the same algebra as before, the A's cancel out and again produce B>=1.

It was probably not clear, but I just meant that the OP should keep the IH as 'P(k) is true for 3 ≤ k < n' instead of 'P(k) is true for 8 ≤ k < n'.

How do the A's cancel?

 

[haruspex]

How do the A's cancel?

$r_n = 1 + r_{\lfloor\sqrt{n}\rfloor} \leq 1 + A + B l_2 l_2 (\lfloor\sqrt{n}\rfloor) \leq 1 + A + B l_2 l_2 (\sqrt{n})$
$= 1 + A + B (l_2 l_2 (n) - 1) = 1 + A -B + B l_2 l_2 (n)$.
If B >= 1, $1 + A -B + B l_2 l_2 (n) \leq A + B l_2 l_2 (n)$.
With A=2, that IH is true for n = 2, 3. The induction takes it from there.

 

[NATURE.M]

Okay what does the A represent ? If I'm not mistaken the B is just c but what's the A term ?
Otherwise I understand what your saying.

 

[haruspex]

Okay what does the A represent ? If I'm not mistaken the B is just c but what's the A term ?
Otherwise I understand what your saying.

A is just adding a sufficient buffer to ensure that the IH is true (with the least possible B) as soon as possible. With A=2 you get to start the IH at n=2. It doesn't affect the asymptotic behaviour.
Making B as low as possible, at the expense of a larger A, gives the asymptotically tightest bound. You could instead start the IH at a higher n₀, but as we have seen that requires a lot more calculation because you have to cover from n₀ to n₀²-1 by hand.

 

[NATURE.M]

A is just adding a sufficient buffer to ensure that the IH is true (with the least possible B) as soon as possible. With A=2 you get to start the IH at n=2. It doesn't affect the asymptotic behaviour.
Making B as low as possible, at the expense of a larger A, gives the asymptotically tightest bound. You could instead start the IH at a higher n₀, but as we have seen that requires a lot more calculation because you have to cover from n₀ to n₀²-1 by hand.

Oh that makes a lot of sense. So more generally, we can write f is in 0(g(n) + A) and it wouldn't actually make a difference since A is only a constant.

 

[SammyS]

...

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 \$ ?

As I mentioned in Post #9 above:

I would have approached this problem somewhat differently. Look at how this sequence progresses.

r₂ & r₃: $\ \lfloor \sqrt{2}\rfloor=\lfloor \sqrt{3}\rfloor=1 \$ Therefore, r₂ = r₃ = 1 + r₁ = 2 .

r₂ and r₃ both refer to r₁, so they have the same value.

The smallest n for which r_n refers to r₂ is n = 4, a perfect square, in fact 2².

The smallest n for which r_n refers to r₃ is n = 9, in fact 3². But r₂ = r₃ there is no increase going from r₈ to r₉.

The smallest n for which r_n refers to r₄ is n = 4² = 16. Note that: r₄ = ... = r₁₅ = 4.

From here, there are a whole slew of n values for which the r_n refer back to these members of the sequence having value of 4. Starting with r₁₆ they all have a value of 5.

The smallest n for which r_n refers to r₁₆ is n = 16² = 256. ...

So, r₁ = 1

r_n increases to 2 when n goes to 2.

r_n increases to 3 when n goes to 4 = 2².

r_n increases to 4 when n goes to 16 = 4² = (2²)².

r_n increases to 5 when n goes to 256 = 16² = ((2²)²)².

You can relate the value of r_n to the overall exponent on 2 for the value of n at which r_n is incremented. Perhaps induction may be used to prove that this relationship holds for each value of n and/or r_n .

 

[haruspex]

As I mentioned in Post #9 above:

I would have approached this problem somewhat differently. Look at how this sequence progresses.

r₂ & r₃: $\ \lfloor \sqrt{2}\rfloor=\lfloor \sqrt{3}\rfloor=1 \$ Therefore, r₂ = r₃ = 1 + r₁ = 2 .

r₂ and r₃ both refer to r₁, so they have the same value.

The smallest n for which r_n refers to r₂ is n = 4, a perfect square, in fact 2².

The smallest n for which r_n refers to r₃ is n = 9, in fact 3². But r₂ = r₃ there is no increase going from r₈ to r₉.

The smallest n for which r_n refers to r₄ is n = 4² = 16. Note that: r₄ = ... = r₁₅ = 4.

From here, there are a whole slew of n values for which the r_n refer back to these members of the sequence having value of 4. Starting with r₁₆ they all have a value of 5.

The smallest n for which r_n refers to r₁₆ is n = 16² = 256. ...

So, r₁ = 1

r_n increases to 2 when n goes to 2.

r_n increases to 3 when n goes to 4 = 2².

r_n increases to 4 when n goes to 16 = 4² = (2²)².

r_n increases to 5 when n goes to 256 = 16² = ((2²)²)².

You can relate the value of r_n to the overall exponent on 2 for the value of n at which r_n is incremented. Perhaps induction may be used to prove that this relationship holds for each value of n and/or r_n .

Seems like a lot more work than the solution already posted.

 

[SammyS]

Seems like a lot more work than the solution already posted.

Perhaps.

... but, it wasn't clear to me that OP had fully comprehended the details of that solution.