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: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook