As per Qiaochu's comment on the answer so far, consider
$a_n = 2 a_{\lfloor n/2 \rfloor} + n^2$
with $a_1 = 1$ and $a_n = 1, 6, 11, 28, 37, 58, 71, 120,\dots$ for $n = 1,2,\dots$. Then
$a_{2n} = 2 a_n + 4n^2 \quad\quad\text{and}\quad\quad a_{2n+1} = 2 a_n + 4n^2 + 4n + 1$
where both recurrences are valid for $n\ge 1$. Working with each recurrence we can use generating functions to obtain a system of functional equations. Let
$f(z) = \sum_{n=1}^{\infty}a_n z^n$
be the generating function for the sequence of $a_n$'s. Working with the first equation we multiply by $z^{2n}$, sum over all $n\ge 1$
$\sum_{n=1}^{\infty}a_{2n}z^{2n} = 2\sum_{n=1}^{\infty}a_n(z^2)^n + \sum_{n=1}^{\infty}4n^2z^{2n}$
and obtain
$ \frac{f(z) + f(-z)}{2} = 2f(z^2) + \frac{4 z^2 \left(1+z^2\right)}{\left(1-z^2\right)^3}$
Working with the second equation, we multiply by $z^{2n+1}$, sum over all $n\ge 1$
$\sum_{n=1}^{\infty}a_{2n+1}z^{2n+1} = 2z\sum_{n=1}^{\infty}a_n(z^2)^n + \sum_{n=1}^{\infty}(4n^2+4n+1)z^{2n+1}$
and obtain
$\frac{f(z)-f(-z)}{2} -z = 2zf(z^2)+\frac{z^3 \left(z^4-2 z^2+9\right)}{\left(1-z^2\right)^3}$
We can obtain a solution by solving these functional equations.
EDIT: Adding the two equations together and simplifying we obtain
$f(z) = \frac{z+z^2}{(1-z)^3} + 2(1+z)f(z^2)$
We can iterate this equation to obtain better and better approximation of $f(z)$. I believe that if we iterate enough times to have $f(z^{2^t})$ as part of the approximation, then the approximation will be exact for the first $2^t-1$ coefficients.