# Is there a formula for the summation of this form?

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

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

So,

$$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$

• I didn't even think about simplifying the expression... Thank you for the help! – Kot Mar 3 '15 at 4:17