(adsbygoogle = window.adsbygoogle || []).push({}); 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 = 2^{k}

This is my way:

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

= 4(f(2^{k-2}) * (2*2^{k}) - 3

:

:

= 2^{j}*f(2^{k-j}) + j2^{k}- (j-1)

Guess: j=k

2^{j}*f(2^{j-j}) + j2^{j}- (j-1)

2^{j}f(1)+ j2^{j}- (j-1)

j2^{j}- (j-1) = j2^{j}- j + 1 = j(2^{j})

The TA way

She did the same thing I did but in the part where we have

= 4(f(2^{k-2}) * (2*2^{k})- 3

she put

= 4(f(2^{k-2}) * (2*2^{k})- 2^{2}+ 1

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

Is her way correct where instead of putting the -3 she put the -2^{2}+ 1 ?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Is this allowed in substitution

**Physics Forums | Science Articles, Homework Help, Discussion**