I am trying to solve this recurrence relation: $T(n) = 7T(\frac{n}{2}) + 18(\frac{n}{2})^2$ which is for Strassen's fast matrix multiplication. However I am stuck on trying to reduce the summation.
I am assuming that $T(1) = 1$ and that $n = 2^m$. So for each iteration, I am dividing $n$ by $2$.
First iteration: $T(n) = 7^2T(\frac{n}{2^2}) + 7 * 18 (\frac{n}{n^2}) + 18 (\frac{n}{2})^2$
Second iteration: $7^3T(\frac{n}{2^3}) + 7^2*18(\frac{n}{2^3})^2 + 7*18(\frac{n}{2^2})^2 + 18(\frac{n}{2})^2$
I've done this for one more iteration to make sure, but the pattern should be obvious by now.
Conjecture: $T(n) = 7^{i+1}T(\frac{n}{2^{i+1}}) + \sum_{j=0}^i (7^j + 18(\frac{n}{2^{i+1}})^2)$
I'll skip the proof since the purpose of this question is to reduce the summation.
Since the initial condition is $T(1) = 1$, that means $\frac{n}{2^{i+1}} = 1$. Rewriting gives me $i = lg(n) -1$ or $i = lg(\frac{n}{2})$.
Then I will get $7^{lg(n)} + \sum_{j=0}^{lg(n)-1}7^j * 18(\frac{n}{2^{lg(n)}})^2$.
Expanding the summation yields: $(7*18) + (7^2 * 18)...+ (7^{lg(n)-1} * 18)$.
Here is where I am stuck. I don't know how to put all of this into an equation without the summation. Maybe this is not possible, then that means my conjecture is wrong. But any advice is appreciated!
You can factor out the common factor of $18$, so you really have $$18(7 + 7^2 +\ldots+ 7^{lg(n)-1}).$$
Now use the fact that $$1+r+r^2+\ldots+r^k = \frac{1-r^{k+1}}{1-r}.$$