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!

Repeated substitution help

  1. Oct 19, 2008 #1
    1. The problem statement, all variables and given/known data


    f(n) = 0 when n=1 and 2f(n/2) + n - 1 when n is otherwise

    2. Relevant equations

    Repeated substitution

    3. The attempt at a solution

    f(n) = 2f(n/2) + n - 1

    = 22f(n/22) + n - 3

    = 23f(n/23) + n - 7

    = 24f(n/24) + n - 15

    Guess: f(n) = 2kf(n/2k) + n - (k-1)

    we know from the recurrence that f(1) = 0, so need n/2k = 0

    so n/2k => n = 2k => lg n = k where lg is not log based 10 but log based 2

    f(n) = 2lg nf(n/2lg n) + n - lg n + 1

    when n = 1

    f(n) = 2lg 1f(n/2lg 1) + 1 - lg 1 + 1 = 1f(1) + 1 + 0 + 1 = 2 so this recurrence cannot be proven,
     
    Last edited: Oct 19, 2008
  2. jcsd
  3. Oct 19, 2008 #2

    Mark44

    Staff: Mentor

    How did you go from this:
    f(n) = 2f(n/2) + n - 1

    to this?

    = 2^2f(n/2^2) + n - 3
     
  4. Oct 19, 2008 #3
    I made a big mistake. Here is what I have after rethinking it:

    f(n) = 2f(n/2) + n - 1

    = 2[2f(n/4) + n/2 - 1) + n -1 = 4f(n/4) + 2n - 3

    = 4[2f(n/8) + n/4 - 1) + 2n -3 = 8f(n/8) + 3n - 7

    = 8[2f(n/16) + n/8 - 1) + 3n -7 = 16f(n/4) + 4n - 15

    Guess: f(n) = 2kf(n/2k) + kn - (k-1)

    we know from the recurrence that f(1) = 0 so need n/2k = 0
    so n/2k => n = 2k => k = lg n where lg is log based 2 not 10

    f(n) = 2lg nf(n/2lg n) + n(lg n) - lg n + 1

    f(1) = 2lg 1f(1/2lg 1) + 1(lg 1) - lg 1 + 1 = 1 so this solution to the recurrence and now I have to prove via induction, and I am stuck here:

    Proof by Induction Help:

    Basis: f(n) = n(lg n) - lg n + 1 so when n = 1 the solution is 1 here so this check out

    Assume: for n-1, prove for n (induction step):

    f(n) = (n-1) (lg (n-1)) - lg (n-1) + 1

    so what would I do now?
     
    Last edited: Oct 19, 2008
  5. Oct 20, 2008 #4

    Mark44

    Staff: Mentor

    OK, now I see that you are applying the formula recursively to itself. I added a missing ] in what I think is the right place. It's not clear to me how this formula helps you, though. If I don't know f(n/4), there's no way I can get f(n).
    Continuing, and adding a missing ] where I think it should go...
    I think you made a mistake in the line above (assuming I have the ] in the right place).
    You should get 8f(n/8) + 2n -5.

    In your next line,
    you are again missing a right bracket, and f(n/16) mysteriously changed to f(n/4)

    After you make a guess at what the formula is, you said this:
    n/2^k = 0 iff n = 0
    n/2^k = 0 DOES NOT IMPLY that n = 2^k

    You've given a recurrence relationship between f(n) and f(n/2). You didn't state what you want to end up with.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Repeated substitution help
Loading...