Intermediate step of the recurrence relation T(n) = 2T(n/2)+ n/log(n)

Question

I need help understanding one intermediate step in solving the following recurrence relation:

Through repeated substitution I have gotten all the way up to:

This is where I am stuck. Everyone says that the second part is equal to

I have tried much manipulation and I cannot figure out how to get here.

So - two questions:

1. Why is the bounds on the sum going from 1 to log(n)?
2. How do you arrive at this summation from the sequence that I have? I know the sequence is also written as

I don't need the solution to the entire recurrence, I know exactly how to solve it from there, just this intermediate step.

Answer 1

You've unfolded your recurrence k times to get to

Which means that n = 2^k so:

1. logging both sides of this equation means log(n) = log(2^k) = k which answers why the summation bound goes to log(n)
2. substitute for n into each term of the summation and you get:

Finally:

The two sides just write the harmonic series in reverse order of eachother.

Answer 2

So first of all such recurrences are solved with Master's theorem. You asked why so here is an explanation.

First question was why do you sum from 1 to log n. Its easy: you start with a number n and each time you reduces it by 2 times. So how fast will it approach to n? After log n times (log means log2 here). If this is not clear substitute your n with 2^k.

Now the second part. Your i-th element is (If the these elementary log operations are not clear for you, you have to refresh your knowledge on logarithms):

Now it should be clear why your solution is equivalent to theirs.