Complete Induction Proof

  • Thread starter NATURE.M
  • Start date
  • #1
301
0

Homework Statement


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

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): 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:

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
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?
 
  • #3
301
0
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?

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).
 
  • #4
818
67
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).
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:
  • #5
301
0
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 log2(log2√n)
 
  • #6
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
But i can't just use the IH directly on rfloor(√(n+1)) .
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?
 
  • #7
301
0
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?
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.
 
  • #8
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
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.
Sorry, I asked the wrong question. I should have asked whether the log function is monotonic.
 
  • #9
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,519
1,124
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.
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 \ ## ?
 
  • #10
301
0
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 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 ?
 
  • #11
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
But lets 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 + rfloor(√n). What do you get? What's an upper bound for that?
 
  • #12
301
0
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?
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) ?
 
  • #13
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
Applying the induction hypothesis: 1 + rfloor(√n) ≤ clog2(log2n)
No, not just 'n' inside the logs on the right. What does n represent in the IH?
 
  • #14
301
0
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.
 
  • #15
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
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 rn ≤ c log2(log2n)). How do you apply that to rfloor(√(n+1))?
 
  • #16
301
0
I mean in rn ≤ c log2(log2n)). How do you apply that to rfloor(√(n+1))?
But that was my initial question ? I'm not sure how to apply it to rfloor(√(n+1)).
 
  • #17
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
But that was my initial question ? I'm not sure how to apply it to rfloor(√(n+1)).
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))?
 
  • #18
301
0
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))?
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.
 
  • #19
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
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 rfloor(√(n+1). I'm not asking you to do anything difficult here.
 
  • #20
301
0
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.
Oh just set it equal to k = floor(√(n+1)). Then rk is ≤ the log term by the IH.
 
  • #21
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
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?
 
  • #22
301
0
So here is my logic (by complete induction)
Induction Hypothesis: rk ≡ 1 + rfloor(√(k)) ≤ clog2(log2k) for 3≤k<n.
Then, rn = 1+ r floor(√(n)). By the IH, we know rfloor(√(n)) ≤ clog2(log2floor(√(n))) since floor(√(n)) < n.
So then we have 1+ r floor(√(n)) ≤ 1 + clog2(log2floor(√(n))). And the log function is increasing, so 1 + clog2(log2floor(√(n))) ≤ 1 + clog2(log2n).

So I think the above should be right for the most part, I'm a bit uncertain what to do with the 1 however.
 
  • #23
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
since floor(√(n)) < n
No, you've thrown away too much. You're only trying to get rid of the floor function.
 
  • #24
301
0
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 rfloor(√n) function, since rfloor(√n) = 1 + rfloor(√(floor(√n)) ≤ clog2(log2floor(√(n))) by IH.

As an aside, thanks for being so patient.
 
  • #25
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
In doing this:
1 + c log2(log2floor(√(n))) ≤ 1 + c log2(log2n).
you've thrown away the √ as well as the floor. Only get rid of the floor.
 
  • #26
301
0
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.
 
  • #27
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
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 = x2, x > 0, (and correcting from '<' to '<=') you are asking whether floor(x) <= x only if x > 1. Is it?
 
  • #28
301
0
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 = x2, 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 + clog2(log2floor(√(n))) ≤ 1 + clog2(log2(√(n))) = 1 + clog2(1/2)(log2(n))
= 1 + clog21/2 + clog2(log2(n)) = clog2(log2(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.
 
  • #29
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,006
7,706
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.
 
  • #30
301
0
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∈ℝ+).
 

Related Threads on Complete Induction Proof

  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
3
Views
717
  • Last Post
Replies
24
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
777
  • Last Post
Replies
7
Views
993
  • Last Post
Replies
12
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
3
Views
1K
Top