Demonstrating Strassen's method using domain transformation: $T(n)=7T(n/2)+an^2$ I want to solve the recurrence for Strassen's method (for multiplying square matrices) with domain transformation and get a closed form. The equation is given below:
$T(n)=b$, at $n=2$
$T(n)=7T(n/2)+an^2$, at $n>2$
I know that since I have to cancel out n/2, I should set $n=2^k$. I'll call that $G(k)$.
$G(k)=7G(k-1)+a(2^k)^2$
Now I'm not sure what to do. The $(2^k)^2$ term is quite confusing. It prevents telescoping or characteristic equations as far as I can tell. It doesn't seem to fit any of the simple forms for generating functions.
 A: At each step, we replace $n$ with $\tfrac{n}{2}$ and scale each term by $7$ as follows:
\begin{align*}
T(n) &= 7T\left(\frac{n}{2}\right) + an^2 \\
7T\left( \frac{n}{2} \right) &= 7^2T\left(\frac{n}{2^2}\right) + \frac{7}{4}an^2 \\
7^2T\left( \frac{n}{2^2} \right) &= 7^3T\left(\frac{n}{2^3}\right) + \left(\frac{7}{4} \right)^2 an^2 \\
7^3T\left( \frac{n}{2^3} \right) &= 7^4T\left(\frac{n}{2^4}\right) + \left(\frac{7}{4} \right)^3 an^2 \\
&~~\, \vdots \\
7^{\log_2 n - 2}T(4) &= 7^{\log_2 n - 1}T(2) + \left(\frac{7}{4} \right)^{\log_2 n - 2} an^2 \\
7^{\log_2 n - 1}T(2) &= 7^{\log_2 n - 1}b \\
\end{align*}
Summing everything together, we observe that the terms telescope, yielding:
\begin{align*}
T(n)
&= 7^{\log_2 n - 1}b + \left(1 + \tfrac{7}{4} + (\tfrac{7}{4})^2 + \cdots + (\tfrac{7}{4})^{\log_2 n - 2} \right)an^2 \\
&= 7^{\log_2 n - 1}b + \frac{(\tfrac{7}{4})^{\log_2 n - 1} - 1}{\tfrac{7}{4} - 1}an^2 \\
&= 7^{\log_2 n - 1}b + ((\tfrac{7}{4})^{\log_2 n - 1} - 1)\tfrac{3}{4}an^2 \\
&= \tfrac{1}{7}b7^{\log_2 n} + (\tfrac{4}{7}(\tfrac{7}{4})^{\log_2 n} - 1)\tfrac{3}{4}an^2 \\
&= \tfrac{1}{7}bn^{\log_2 7} + (\tfrac{4}{7}n^{\log_2 7/4} - 1)\tfrac{3}{4}an^2 \\
&= \tfrac{1}{7}bn^{\log_2 7} + \tfrac{3}{7}an^{2 + \log_2 7/4} - \tfrac{3}{4}an^2 \\
&\in \Theta(n^{\log_2 7})
\end{align*}
