# Homework Help: Is this allowed in substitution

1. Oct 26, 2008

1. The problem statement, all variables and given/known data
I have recurrence relation problem and what to ask would my way be just as correct as the TA did the solution:

f(n) = 0, n=1 and 2f(n/2) + n -1

3. The attempt at a solution

Here we assume n = 2k

This is my way:

f(k-1) = 2[2f(2k-2)*2k-1-1] + 2k - 1

= 4(f(2k-2) * (2*2k) - 3
:
:
= 2j*f(2k-j) + j2k - (j-1)

Guess: j=k
2j*f(2j-j) + j2j - (j-1)
2jf(1)+ j2j - (j-1)

j2j - (j-1) = j2j - j + 1 = j(2j)

The TA way

She did the same thing I did but in the part where we have
= 4(f(2k-2) * (2*2k) - 3

she put

= 4(f(2k-2) * (2*2k) - 22 + 1

where my guess came to be j(2j) she gets 2j(j-1) +1

Is her way correct where instead of putting the -3 she put the -22 + 1 ?

Last edited: Oct 26, 2008
2. Oct 26, 2008

### jhicks

I don't understand what you wrote. Can you rephrase? I fail to see the "recurrence".

3. Oct 27, 2008

### HallsofIvy

Do you mean f(n)= 2f(n/2)+ n- 1?

Why k-1? If n= ek, tnen f(n)= f(2k-1). How did you reduce it to "f(k-1)"? Putting n= 2k would give n/2= 2k-1. Is that what you meant?
Are you relabeling f(n)= f(2k) as f(k)? That can be done but you must say so: and it would be better to use a different symbol as you now have a different function: let g(k)= f(2[/sup]k[/sup]). And, of course, since most natural numbers are NOT powers of 2, letting k be a natural number will not give all values of n.

4. Oct 27, 2008

Sorry for the confusion. You right when you stated that when n=2k that f(n/2) becomes f(2k/2) which goes to f(2k-1).

For the f(n-1) I may have skipped a step when substitution. I meant to say:
f(k) =2f(2k-1). + 2k -1

then after that I started my substitution. My qeustion was that when I did my first subsititution I got: 4(f(2k-2) * (2*2k) - 3 where the TA got 4(f(2k-2) * (2*2k) - 22 + 1

I mean naturally - 22 + 1 = -3 but can you do that in substitution? It seems like you are forcing the problem.

Also, you are right that if "letting k be a natural number will not give all values of n". The reason, I believe, that we are letting that happen is because this is a merge sort recursion (sorry again, did not realize that I post in my first post) and that you what any size list that is going in to merge sort to be divide fairly even. I do not know why, but professor could have but the floor symbol or ceiling symbol on the n/2 and that would do it.