How to find a closed form solution to a recurrence of the following form? I need to find the closed form solution to the following recurrence -:
$ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a pattern out for this recurrence. Letting 0.25 to behave as a variable x, I have,
$T(n) = T(n/2) + n^2*x$
$T(2) = 8 + 2^2 * x $
$T(4) = 8*(8 + 2^2 * x) + 4^2 * x $
$T(8) = 8*(8*(8 + 2^2 * x) + 4^2 * x) + 8^2 * x $
I extracted the highest power of 8 from the above equation for T(8), to check if I can find a pattern but couldn't how can I possibly solve this recurrence?
 A: Each $i$ with $1\le i\le j$ contributes $8^{j-i}(2^i)^2x$ to the value of $T(2^j)$, and we get $8^j$ for the base case. So we must have
$$ T(2^j) = 8^j + \sum_{i=1}^j 8^{j-i}(2^i)^2 x = 8^j + \sum_{i=1}^j 4^j 2^{j-i} x
= 8^j + 4^jx \sum_{k=0}^{j-1} 2^k = 8^j + 4^j(2^j-1)x$$
or, reinserting $n=2^j$,
$$ T(n) = n^3 + n^2(n-1)x $$
when $n$ is a power of 2.
A: You may be interested to know that the  recurrence
$$ T(n) = 8\;T(\lfloor n/2 \rfloor) + 1/4 \; n^2 $$
where $T(0) = 0$ and $T(1) = 1/4$ actually has a closed form solution for all $n$ and not just for $n$ a power of two. (We will show how to solve this with $T(1) = 1$ at the end of this post.)
This closed form is obtained by unrolling the recursion according to the binary digits of $n.$ Let those digits be given by 
$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Then the closed form solution (exact for all $n$) is given by
$$ T(n) = \frac{1}{4} \sum_{k=0}^{\lfloor \log_2 n \rfloor} 8^k
\left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} d_j 2^{j-k} \right)^2.$$
To get an upper bound consider the case of all one digits, which gives
$$ T(n) \le  \frac{1}{4} \sum_{k=0}^{\lfloor \log_2 n \rfloor} 8^k
\left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} 2^{j-k} \right)^2 =
\frac{20}{21} 8^{\lfloor \log_2 n \rfloor}
- 4^{\lfloor \log_2 n \rfloor}
+ \frac{1}{3} 2^{\lfloor \log_2 n \rfloor}
- \frac{1}{28}.$$
This bound is attained.
To get a lower bound consider the case of a one digit followed by a string of zeros, giving
$$ T(n) \ge  \frac{1}{4} \sum_{k=0}^{\lfloor \log_2 n \rfloor} 8^k
\left( 2^{\lfloor \log_2 n \rfloor-k} \right)^2 
= \frac{1}{2}  8^{\lfloor \log_2 n \rfloor}
- \frac{1}{4} 4^{\lfloor \log_2 n \rfloor}.$$
This bound too is attained.
Joining these two it now becomes evident that
$$T(n)\in \Theta\left(8^{\lfloor \log_2 n \rfloor}\right)
= \Theta\left(2^{3\lfloor \log_2 n \rfloor}\right)
= \Theta(n^3).$$
The above calculation has $T(1) = 1/4$ while the query asks for $T(1) = 1$. It is not difficult to see that the answer to the original query can be obtained by taking
$$ T(n) + \frac{3}{4} 8^{\lfloor \log_2 n \rfloor}.$$
This gives the following upper and lower bounds
$$ \frac{143}{84} 8^{\lfloor \log_2 n \rfloor}
- 4^{\lfloor \log_2 n \rfloor}
+ \frac{1}{3} 2^{\lfloor \log_2 n \rfloor}
- \frac{1}{28}
\quad\text{and}\quad
\frac{5}{4}  8^{\lfloor \log_2 n \rfloor}
- \frac{1}{4} 4^{\lfloor \log_2 n \rfloor}.$$
The asymptotic complexity is not affected.
There is more material on this method here.
A: [EDIT: it seems the question is restricted to powers of $2$ where the integer and real recurrence are the same. With that restriction the following is a complete solution, but is aimed at the unrestricted problems, for general integer or real values of $n$]
As usual with these algorithm recurrences, the smoothed problem where real-valued $\frac{n}{2}$ is used instead of  integer $n$ DIV $2$, has a cleaner solution and tells the asymptotics.  There might be a chance of a closed form for the the integer problem if you write everything in binary digits of $n$.  For the smoothed problem this one has a nice answer.
Writing $T(n) = n^3 x S(n)$ removes the difficulty with the $8$ and cleans up the $x$ in the last term.  $$S(n) = S(n/2) + \frac{1}{n}$$. 
Observe that $S_0(n)=\frac{-1}{n}$ is a solution.
The general solution is to add a solution of $f(n)=f(n/2)$ to $S_0$.
Conclusion:

$$T(n) = x(-n^2 + n^3f(n))$$ where $f$ is a function with $f(n)=f(n/2) \quad$  [equivalently, $f(2^x)$ has period $1$] 

This means that if in the integer problem you start the recurrence at large enough $n$, prescribing the early values arbitrarily, the asymptotics are $T(n) = Cn^3 + O(n^2)$ with $C$ determined by the early values.  In fact $C$ will be a linear function of those values, a simple enough thing in principle, but the coefficients are potentially quite complicated.
[EDIT: in the restricted problem with powers of $2$,the function $f(n)$ is a constant. To fit $T(1)$ the constant should be selected so that $T(1)=x(-1 + f)$.  Then $T(n)=x(n^3 - n^2) + n^3 x (f-1) = x(n^3 - n^2) + T(1)n^3$.]
A: Without converting 0.25 to a variable x, I found that T(n) = $8^{log_2n}(1+\sum_{i=0}^n\frac{1}{8x})$, but whether that's a closed form I don't know 
