# Repeated substitution help

1. Oct 19, 2008

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. Oct 19, 2008

### Staff: Mentor

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

to this?

= 2^2f(n/2^2) + n - 3

3. Oct 19, 2008

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
4. Oct 20, 2008

### 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.