Let $T(n) = 3T(\frac{n}{2}) + n^2$. Solve for $T(n)$ without using Master Theorem.
My try: I used substitution and got $$T(n) = 3^kT(\frac{n}{2^k}) + \sum_{l = 0}^{k-1} (\frac{3}{4})^ln^2$$ where $k \in \mathbb{N}$. What's the next step? Maybe geometric series is helpful. The answer should be $T(n) = \Theta(n^2)$.
Change variables: $n = 2^k$, $k = \log_2 n$; $t(k) = T(2^k)$. You get:
$\begin{align*} t(k) &= 3 t(k - 1) + 2^{2 k} \\ \frac{t(k)}{3^k} - \frac{t(k - 1)}{3^{k - 1}} &= \frac{2^k}{3^k} \\ \frac{t(k)}{3^k} &= 3^k \cdot \sum_{1 \le r \le k} \left(\frac{2}{3}\right)^r + \frac{t(0)}{3^0} \\ t(k) &= 3^k \cdot \left( \sum_{1 \le r \le k} \left(\frac{2}{3}\right)^r + t(0) \right) \end{align*}$
The sum inside parenteses converges when $k \to \infty$ (to 3), so this is bounded by $t(0) \le \text{sum} \le 3 + t(0)$:
$\begin{align*} T(n) &= \Theta(3^{\log_2 n}) \\ &= \Theta(n^{\log_2 3}) \end{align*}$
The last one by:
$\begin{align*} 3^{\log_2 n} &= \left( 2^{\log_2 3} \right)^{\log_2 n} \\ &= \left( 2^{\log_2 n} \right)^{\log_2 3} \\ &= n^{\log_2 3} \end{align*}$
($x^{\log y}$ is conmutative ;-)