Strong Induction Proof with a Floor

[Temp0]

Homework Statement

are[/B]
a_n = a_floor(n-2) + a_floor(2n/3) + n
a₀ = 1
Prove that for all n ≥ 3, a_n > 4n

Homework Equations

The Attempt at a Solution

Since this is induction, I start out with a base case:
Base Case (n = 3):
a₃ = a₁ + a₂ + 3 = 3 + 8 + 3 = 14
4(n) = 4(3) = 12
14 > 12
Therefore, the base case is true. a₃ > 4(3)

Inductive Hypothesis: Let some integer m ≥ 3 and assume a_m > 4m for all integers m. Also assume there is an integer k, where k > 4, so that 3 ≤ m ≤ k

Inductive Step:
We want to prove that a_k+1 > 4(k+1)
Starting out with writing the equation of a_k+1:
a_k+1 = a_{floor( (k+1) / 2 )} + a_{floor( 2(k+1)/3 )} + k + 1
By the inductive hypothesis: Since floor( (k+1)/2 ) and floor (2(k+1)/3) are both between 3 and k, we can assume that:
a_{floor( (k+1) / 2 )} and a_{floor( 2(k+1)/3 )} are both greater than 4 floor( (k + 1)/2) and 4floor( 2(k+1)/3) respectively. Therefore, all I have to do is prove that:

4 floor ( (k + 1)/2) + 4 floor ( 2(k+1)/3) + k + 1 > 4(k+1)
However, I am stuck on this step, I know I just have to simplify this equation, but up until now, I've been proving these types of equations without the floor in it, so I can just simplify with algebra and prove the inequality. Could anyone clarify how I would continue this solution? Thank you in advance.

 

[haruspex]

Inductive Hypothesis: Let some integer m ≥ 3 and assume a_m > 4m for all integers m. Also assume there is an integer k, where k > 4, so that 3 ≤ m ≤ k

That could be worded rather better. It doesn't say what you need it to say.

Inductive Step:
We want to prove that a_k+1 > 4(k+1)
Starting out with writing the equation of a_k+1:
a_k+1 = a_{floor( (k+1) / 2 )} + a_{floor( 2(k+1)/3 )} + k + 1
By the inductive hypothesis: Since floor( (k+1)/2 ) and floor (2(k+1)/3) are both between 3 and k, we can assume that:
a_{floor( (k+1) / 2 )} and a_{floor( 2(k+1)/3 )} are both greater than 4 floor( (k + 1)/2) and 4floor( 2(k+1)/3) respectively. Therefore, all I have to do is prove that:

4 floor ( (k + 1)/2) + 4 floor ( 2(k+1)/3) + k + 1 > 4(k+1)
However, I am stuck on this step, I know I just have to simplify this equation, but up until now, I've been proving these types of equations without the floor in it, so I can just simplify with algebra and prove the inequality. Could anyone clarify how I would continue this solution? Thank you in advance.

What's a lower bound for floor((n+1)/2)?

 

[Temp0]

Hmm I'm not sure, I don't think I've ever learned that yet, and I'm trying to figure it out now. So far, what I know about the boundaries of floors is this:

If x is some real number, and the floor of x is n, then n ≤ x < n+1

Also, could you clarify on how my induction hypothesis is bad?

Edit: Now that I think about it, could the lower bound of a floor be x - 1? Then the inequality would look like:

x - 1 ≤ n ≤ x < n+1

 

[haruspex]

Edit: Now that I think about it, could the lower bound of a floor be x - 1?

Yes.

Also, could you clarify on how my induction hypothesis is

You wrote "assume a_m > 4m for all integers m (>2)", but that is what you are trying to prove. Then "assume there exists k >= n", which is vacuously true. There should be an upper bound on m, namely, k.

 

[Temp0]

Hmm, I see, but don't I say that at the end when I put

3 ≤ m ≤ k ?

 

[haruspex]

Hmm, I see, but don't I say that at the end when I put

3 ≤ m ≤ k ?

No. You wrote

assume there is an integer k, where k > 4, so that 3 ≤ m ≤ k

I.e., you have picked some integer m and are now "assuming" there is a larger one. How could there not be a larger one?
Please try to rewrite your inductive hypothesis correctly. It is important to be able to get this right.

 

[Temp0]

Ohh, I see! Yup, my professor usually writes it like that so I guess I copied him, it does make sense, there is always a larger number so I guess it's pointless to assume there to be a larger one.

 

[haruspex]

Ohh, I see! Yup, my professor usually writes it like that so I guess I copied him, it does make sense, there is always a larger number so I guess it's pointless to assume there to be a larger one.

Ok, so can you figure out how to write it correctly? The style is pretty standard.

 

[Temp0]

Hmm it's kind of hard because my induction hypothesis came from my notes where the general idea was to assume that everything within the range of the lower boundary to the upper boundary (k) is assumed to be true, and then I needed to prove that the equation works for k + 1 in my induction step. Which is why I put the whole assume a_m > 4m thing. Don't I need one of these for my hypothesis in strong induction?

 

[haruspex]

Hmm it's kind of hard because my induction hypothesis came from my notes where the general idea was to assume that everything within the range of the lower boundary to the upper boundary (k) is assumed to be true, and then I needed to prove that the equation works for k + 1 in my induction step. Which is why I put the whole assume a_m > 4m thing. Don't I need one of these for my hypothesis in strong induction?

Yes, that's the basic structure, but the details matter. It should take the form "suppose that for some integer k the IH is true for every integer 2 <= m < k". Do you see the difference? Basically, you must pick the upper limit first.

 

[Temp0]

Ohh, i didn't know that mattered, I'll keep that in mind for all future proofs, I think i have the right idea now, i'll just put it onto paper and see if I can solve it and the other problems. Thank you very much for all the assistance!

 

[haruspex]

Ohh, i didn't know that mattered

I don't want you to get the impression this is just a matter of style. It's a matter of constructing a logical argument. The way you posted it, the logic does not work at all.