I had this equation for calculating this recursion:
$$ T(n) = 4T(\frac{n}{2}) + n $$
I'm using a recursion tree to solve this, it's similar to this one:
But anyway what matters is that from the recursion equation I have the following sum:
$$\sum_{i=0} ^ {log_2 n - 1} 4^i * n.$$
Applying the property:
$$\sum_{i=0} ^ {k} x^i = \frac{x^{k+1} - 1}{x - 1}$$
We have
$$\sum_{i=0} ^ {log_2 n - 1} 4^i = \frac{4^{log_2 n} - 1}{4 - 1};$$
from there the solution manual states that
$$ \frac{4^{log_2 n} - 1}{4 - 1} = \frac{{n^2} - 1}{3}.$$
How come? $$ 4^{log_2 n} = n^2 $$
Because using the definition of logarithm and properties of exponents,
$4^{\log_2n}=(2^2)^{\log_2n}=2^{2\log_2n}=2^{(\log_2n)2}=(2^{\log_2n})^2=n^2$.