How Does Repeated Substitution Solve the Recurrence Relation f(n)?

[Ad2d]

Homework Statement

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

Homework Equations

Repeated substitution

The Attempt at a Solution

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

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

= 2³f(n/2³) + n - 7

= 2⁴f(n/2⁴) + n - 15

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

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

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

f(n) = 2^{lg n}f(n/2^{lg n}) + n - lg n + 1

when n = 1

f(n) = 2^{lg 1}f(n/2^{lg 1}) + 1 - lg 1 + 1 = 1f(1) + 1 + 0 + 1 = 2 so this recurrence cannot be proven,

 

[Mark44]

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

to this?

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

 

[Ad2d]

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) = 2^kf(n/2^k) + kn - (k-1)

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

f(n) = 2^{lg n}f(n/2^{lg n}) + n(lg n) - lg n + 1

f(1) = 2^{lg 1}f(1/2^{lg 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?

 

[Mark44]

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

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

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

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

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,

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

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:

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

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.