1. Not finding help here? Sign up for a free 30min 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!

Induction Inequality Question

Tags:
  1. Aug 2, 2017 #1
    1. The problem statement, all variables and given/known data
    a0 = 0, and for n > 0, $$a_n = a_{\frac {n} {5}} + a_{\frac {3n} {5}} + n $$

    For the above equation, besides an, the subscripts are floored

    Prove that an ≤ 20n
    2. Relevant equations

    See above.

    3. The attempt at a solution

    I know how to do the question, my problem is starting it. It's strong induction vs. induction. I am leaning towards strong induction due to the first equation having multiple conditions. I would assume that my base case then would be n=0 and n=1
     
  2. jcsd
  3. Aug 3, 2017 #2
    Cannot edit my solution attempt, ignore what I put there.

    3. The attempt at a solution

    Questioning myself on strong induction, but I committed to it.

    Base case of 0 and 1 are good.

    Inductive Hypothesis: $$ a_k \leq 20k $$

    Proof:

    Want to prove $$a_{k+1} \leq 20(k+1) $$

    $$a_{k+1} = a_{\frac {k+1} {5}} + a_{\frac {3k+3} {5}}+ k + 1 $$

    I am getting stuck at this point, don't really know where to go from here. The floors of the subscripts are what is confusing me
     
    Last edited: Aug 3, 2017
  4. Aug 3, 2017 #3

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Are you sure that this is true?
     
  5. Aug 3, 2017 #4

    RUber

    User Avatar
    Homework Helper

    I recommend you look at it this way:
    ##a_k = a_{\left\lfloor \frac{k}{5} \right\rfloor} +a_{\left\lfloor \frac{3k}{5} \right\rfloor} + k##
    assume
    ##a_k \leq 20k ##
    Then show that
    ##a_{k+1} \leq a_k + 20 \leq 20(k+1).##
     
  6. Aug 3, 2017 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Hint: besides the suggestion in #4, you should remember that ##\lfloor x/5 \rfloor## increases by 1 when ##x## passes through integers of the form ## 5n## and ##\lfloor 3x/5 \rfloor## increses by 1 when ##x## passes through integers of the form ##5n/3##.
     
  7. Aug 3, 2017 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    you mean, assume an≤20n ∀ n≤k, right?
    (Seems to me the factor 20 specified is unnecessarily large. It could have been set at 5.)
     
  8. Aug 4, 2017 #7

    RUber

    User Avatar
    Homework Helper

    That's exactly what I meant. It has to be true for all the terms up to and including the current one, then you can inductively prove it for the next one ##a_{k+1}##.

    If the floor function is confusing, sometimes you can just get rid of it.
    Remember that the floor function is always less than what is applied to.
    ##\lfloor 12/5 \rfloor \leq 12/5 ##
    So if ## a_n \leq 20n \forall n\leq k ##, then you can say that ## a_{k/5} \leq 20(k/5) ## dropping the floor part out.

    In doing this, although not the most refined technique, you can eliminate what was confusing you. Then you have an algebraic proof. You will end up needing to satisfy some condition for a minimum number that k has to be greater than. Smaller terms you can demonstrate explicitly.
     
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: Induction Inequality Question
  1. Induction inequality (Replies: 1)

Loading...