# Strong Induction Proof with a Floor

1. Mar 1, 2015

### Temp0

1. The problem statement, all variables and given/known data are
an = afloor(n-2) + afloor(2n/3) + n
a0 = 1
Prove that for all n ≥ 3, an > 4n
2. Relevant equations

3. The attempt at a solution
Since this is induction, I start out with a base case:
Base Case (n = 3):
a3 = a1 + a2 + 3 = 3 + 8 + 3 = 14
4(n) = 4(3) = 12
14 > 12
Therefore, the base case is true. a3 > 4(3)

Inductive Hypothesis: Let some integer m ≥ 3 and assume am > 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 ak+1 > 4(k+1)
Starting out with writing the equation of ak+1:
ak+1 = afloor( (k+1) / 2 ) + afloor( 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:
afloor( (k+1) / 2 ) and afloor( 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.

2. Mar 2, 2015

### haruspex

That could be worded rather better. It doesn't say what you need it to say.
What's a lower bound for floor((n+1)/2)?

3. Mar 2, 2015

### 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

4. Mar 2, 2015

### haruspex

Yes.
You wrote "assume am > 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.

5. Mar 2, 2015

### Temp0

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

3 ≤ m ≤ k ?

6. Mar 2, 2015

### haruspex

No. You wrote
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.

7. Mar 2, 2015

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

8. Mar 3, 2015

### haruspex

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

9. Mar 3, 2015

### 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 am > 4m thing. Don't I need one of these for my hypothesis in strong induction?

10. Mar 3, 2015

### haruspex

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.

11. Mar 3, 2015

### 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!

12. Mar 3, 2015

### haruspex

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.