# Recurrence Relation help

1. Oct 12, 2011

### seansrk

[PLAIN]http://img442.imageshack.us/img442/4514/ballsp.jpg [Broken]
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.

Last edited by a moderator: May 5, 2017
2. Oct 12, 2011

### 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?

3. Oct 12, 2011

### seansrk

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.