1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Strong Induction Proof with a Floor

  1. Mar 1, 2015 #1
    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. jcsd
  3. Mar 2, 2015 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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)?
     
  4. Mar 2, 2015 #3
    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
     
  5. Mar 2, 2015 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  6. Mar 2, 2015 #5
    Hmm, I see, but don't I say that at the end when I put

    3 ≤ m ≤ k ?
     
  7. Mar 2, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  8. Mar 2, 2015 #7
    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.
     
  9. Mar 3, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Ok, so can you figure out how to write it correctly? The style is pretty standard.
     
  10. Mar 3, 2015 #9
    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?
     
  11. Mar 3, 2015 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  12. Mar 3, 2015 #11
    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!
     
  13. Mar 3, 2015 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Strong Induction Proof with a Floor
  1. Induction proof (Replies: 1)

  2. Proof By Induction (Replies: 2)

  3. Proof by induction (Replies: 1)

  4. Proof by Induction (Replies: 3)

Loading...