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

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