How does the n drop down in this recurrence relation problem?

[seansrk]

[PLAIN]http://img442.imageshack.us/img442/4514/ballsp.jpg
The base case is 2^{K} = n (which turns into log_{2}n = k

So I have a question on this recurrence relation problem. (I'm trying to get to make the top equation look like the bottom equation.) I know that the summation ends up becoming

\frac{((7/4)^K)-1}{(7/4)-1}

which gives us
((7/4)^log_{2}n)-1 / (3/4)

I'm lost on how the n drops down. I know how the (log[2]7-2)-1 comes to be but how does the n and log[2]7 -2 get on the same level and the exponent level disappeared?

Hopefully I didn't make this confusing. Just trying to find out how the n came down.

 

[HallsofIvy]

Your basic problem is that the first sum depends upon the value of "k" but there is no "k" in the second. What happened to it? And, since there is no "n" in the sum (ignore the "n^2" for the moment), how do you get that "n" in the numerator of the second formula?

 

[seansrk]

Your basic problem is that the first sum depends upon the value of "k" but there is no "k" in the second. What happened to it? And, since there is no "n" in the sum (ignore the "n^2" for the moment), how do you get that "n" in the numerator of the second formula?

Well previously in the problem it was stated that 2^k = n. Which using the rules of logs we turned that into k = log base 2 n. So when we got the (7/4)^k what I did was i substituted log base 2 n into k giving us the n. in the exponent.