Recurrence Relation for Strassen I'm trying to solve the following recurrence relation (Strassen's):-
$$
T(n) =\begin{cases} 7T(n/2) + 18n^2 &   \text{if } n > 2\\
      1               &   \text{if } n \leq 2
\end{cases}
$$
So I multiplied the $7$ by $2$ several times and the 18n^2^2 several times and ended up with this general equation:-
$$
7k T(n/2^k) + 18n^2k
$$
but, well, firstly, is this correct? and also, how do I find the value of k from that beast?!
Many thanks in advance everyone, I really appreciate all your help.
 A: Write $n = 2^k$ and define $U_k = T(2^k)$.  The relation beocmes
$$U_k - 7\, U_{k-1} = 18 \cdot 2^{2 k}$$
with the initial condition being
$$U_1 = 1$$
I broke the equation up into a homogeneous solution and an particular solution, then applied the initial condition, as follows:
$$U_k = H_k + P_k$$
$$H_k - 7 H_{k-1} = 0 \implies H_k = A \cdot 7^k$$
Choose $P_k = B \cdot 4^k$; then
$$B \cdot 4^k - \frac{7}{4} B \cdot 4^k = 18 \cdot 4^k \implies B = -24$$
Then $U_k =  A \cdot 7^k - 24 \cdot 4^k$.  Use $U_1=1$ to get that 
$$7 A - 96 = 1 \implies A = \frac{97}{7}$$
The result is
$$U_k =97 \cdot 7^{k-1} -96 \cdot 4^{k-1}$$
To recover $T(n)$, substitute $k=\log_2{n}$ into $U_k$.  The result is
$$T(n) = \frac{97}{7} n^{\log_2{7}} - 24 n^2$$
A: We can actually obtain exact values for $T(n)$ for all values of $n$ and not just powers of two.
Start by working with the alternate recurrence relation
$$S(n) = 7 S(\lfloor n/2 \rfloor) + 18n^2$$
where $S(0) = 0.$
Let the binary representation of $n$ be given by
$$ n = \sum_{k=0}^{\lfloor \log_2 n\rfloor} d_k 2^k.$$
Then it is not difficult to see that the exact value of $S(n)$ is given by
$$ S(n) = 18 \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j 
\left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} d_k 2^{k-j}\right)^2.$$
Now to get an upper bound on $S(n)$ consider the case where $n$ consists of all one digits, giving
$$ S(n) \le 18 \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j 
\left( \sum_{k=j}^{\lfloor \log_2 n\rfloor} 2^{k-j} \right)^2 =
\frac{441}{5} 7^{\lfloor \log_2 n\rfloor}-96 \times 4^{\lfloor \log_2 n\rfloor} +
\frac{144}{5} 2^{\lfloor \log_2 n\rfloor} -3.$$
For a lower bound, take $n$ to be a one digit followed by zeros, giving
$$ S(n) \ge 18 \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j 
(2^{\lfloor \log_2 n\rfloor-j})^2 =
42 \times 7^{\lfloor \log_2 n\rfloor} - 24 \times 4^{\lfloor \log_2 n\rfloor}.$$
We still need to account for the fact that $T(0)=1, T(1)=1$ and $T(2)=1.$ A simple calculation shows that
$$ T(n) = S(n) - \frac{197}{7} 7^{\lfloor \log_2 n\rfloor} d_{\lfloor \log_2 n\rfloor}
+ 78 \times 7^{\lfloor \log_2 n\rfloor-1} d_{\lfloor \log_2 n\rfloor-1}.$$
This formula is exact and holds for all $n\ge 3$.
Finally to get the asymptotics look at the two leading terms from the lower and upper bounds. The first is
$$\Theta\left(7^{\lfloor \log_2 n\rfloor}\right) =
\Theta(2^{\log_2 7 \log_2 n}) = \Theta(n^{\log_2 7}).$$
$T(n)$ fluctuates around this value with the coefficient at most for strings of ones
$$\frac{1}{7} \left(\frac{441}{5} - \frac{197}{7} + \frac{78}{7} \right)= \frac{356}{35}$$
and at least
$$ 42 - \frac{197}{7} = \frac{97}{7}.$$
The next term in the asymptotic expansion is
$$\Theta\left(4^{\lfloor \log_2 n\rfloor}\right) = \Theta(n^2),$$
with the coefficient between $24$ and $96.$
