Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to solve this recurrence

  1. Jul 16, 2012 #1
    1. The problem statement, all variables and given/known data

    Solve the recurrence: T(n) = T(n/7) + T(4n/5) + n for n > 35 with base case T(n) = constant for n ≤ 35.


    2. Relevant equations



    3. The attempt at a solution

    Is this mathematical induction? No idea how to do this one.
     
    Last edited: Jul 16, 2012
  2. jcsd
  3. Jul 16, 2012 #2

    HallsofIvy

    User Avatar
    Science Advisor

    You seem to be missing a "=". Where is it supposed to be?
     
  4. Jul 16, 2012 #3
    Hi XodoX, it does look like a recurrence, except, as HallsofIvy is pointing, the recurrence rule is missing.
    Is this T(n+1)=T(n)+T(n/7)+T(4n/5)+n ? (T(36)=3c+35)
    if it is, what when n is not a multiple of 7 and 4n is not a multiple of 4 ? we take the floor / ceiling ? do you have some context around this question ?

    Cheers...
     
  5. Jul 16, 2012 #4
    Fixed it. Sorry, wrong button.
     
  6. Jul 16, 2012 #5
    Still, is 36/7=5 ? is 144/5=28 ?
    just to make sure we are solving the right problem, do you have some context around this puzzle ?

    Cheers...
     
  7. Jul 17, 2012 #6
    No, nothing else. So plug in numbers? But the equation does not hold up. I don't get it.
     
    Last edited: Jul 17, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook