I have the following recurrence relation to solve: $T(n) = 2\cdot T(n/4) + n^2$, $T(1) = 1$. This seemed pretty innocuous at first, after the first three steps, not so much.
(1) given above
(2) $2^2 T(n/4^2) + n^2 + 2(n/4)^2$
(3) $2^3 T(n/4^3) + n^2 + 2(n/4)^2 + 2^2(n/4^2)^2$
I saw the last part as a geometric series: with $r = \frac{2^k}{4^2k} $, $a = n^2$. So I used $\frac{a}{1-r}$ to compute the sum, which after simplification became $n^2(1 - 2^{k-1})$. This implies $$T(n) = 2^k T(n/2^2k) + n^2(1 - 2^{k-1}).$$
Ultimately, this led me to solving the recurrence as: $2^{1/2} n (1 + n^2) + 3n^2$. But wolfram alpha solved it as: $$T(n) = (8n^2 - n^{1/2})/7.$$
As wolphram has worked for past problems, I think the error lies with on my end. I would appreciate if someone could help correct the error of my ways.
(Note: I originally had $n=2^k$ here. Since there is no $T(n/2)$, I should have chosen $n=4^k$ instead. I have corrected this and completed the solution.)
Try letting $n=4^k$ (in the case where $n$ is a power of 4). Then you get the equation $$T(4^k)=2\cdot T(4^{k-1}) + 16^k, ~~~T(4^0) = 1.$$ ($n^2=(4^k)^2=(4^2)^k=16^k$.) Now let $S(k) = T(4^k)$. Then you have $$S(k) = 2 \cdot S(k-1) + 16^k, ~~~S(0) = 1.$$
Now solve this, and rewrite in terms of $n$.
The homogeneous equation is $H(k) = 2 \cdot H(k-1)$, whose solution is easily seen to be $$H(k)=c_1 \cdot 2^k.$$ There are no $16^k$'s in this, fortunately, so a particular solution $P(k)$ to the equation of the form $A\cdot 16^k$ can be found. Substituting yields $A=\frac87$, and $P(k)=\frac87 \cdot 16^k$. Thus, $$S(k)=H(k)+P(k)= c_1 \cdot 2^k + \frac87\cdot 16^k$$ and the condition that $S(0)=1$ implies that $c_1=\frac{-1}7$. Thus $$S(k) = \frac{-1}7 \cdot 2^k + \frac87\cdot 16^k.$$ Now, $n=4^k$, so $$T(n)=T(4^k)=S(k) = \frac{-1}7 \cdot 2^k + \frac87\cdot 16^k =\frac{-1}7 \cdot \sqrt n + \frac87\cdot n^2.$$ Reassuringly, this is the same formula that WolframAlpha gives.
Check that the answer works for non-powers-of-4.
It's clear that $T(1)=1$. Substituting the formula into the original recurrence simplifies to $=0$. QED