I am doing recurrence relations and I have done some work to get the summation $$\sum\limits_{i=0}^{k-1}16^{i}\left(\dfrac{n}{4^i}\right)^2.$$ I know that there is a formula if the summation was just $16^i$ but I do not remember if there was actually a formula for summations with this form. I was thinking about splitting up the summation because it was a product of two expressions but I remember reading somewhere that it isn't allowed. I typed this summation into wolframalpha and got WolframAlpha. I am assuming there is a formula or rule for doing this summation but I am not sure where to find it.


1 Answer 1


$$\left(\frac{n}{4^i}\right)^2 = \frac{n^2}{4^{2i}}=\frac{n^2}{16^i}$$


$$16^i\left(\frac{n}{4^i}\right)^2 = n^2$$

As the summands simplify to not depend on $i$, you multiply by the number of iterations on the sum, for a total of $kn^2$

  • $\begingroup$ I didn't even think about simplifying the expression... Thank you for the help! $\endgroup$
    – Kot
    Mar 3, 2015 at 4:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .