I've developed a general solution for the above-cited recurrence for
$$ f(n)=\sum_j c_j n^{k_j} $$
That is, $f(n)$ is a polynomial in powers of $n$. The solution was carried out with the standard substitution, $n=b^m$ to get
$$ S(m)=S(m-1)+f(b^m) $$
and then by induction to get
$$ S_m=a^m\bigg[S_0+\sum_j c_j\frac{B_j}{B_j-1}\big( B_j^m-1\big) \bigg]\\ $$
$$ T_n=a^{\log_bn}\bigg[T_1+\sum_jc_j \frac{B_j}{B_j-1}\big( B_j^{\log_bn}-1\big) \bigg] $$
where $B_j=b^{k_j}/a$, and it is understood that
$$ \lim_{B\to1}\frac{B}{B-1}\big(B^m-1 \big)=1 $$
(For a more general solution to $S(m)$ with arbitrary $f(n)$, see my post here.)
Now, the point here is that nowhere in the derivation, except for the induction, where $m=1,2,3,\ldots$, did we specify any restrictions on the parameter values for $[a, b, c, k]$. In fact, once we have the solution for $S(m)$ we can use any value of $m$ (e.g., analytic continuation). In addition, any of the parameters can be real or complex. (The parameter space has not been fully mapped, however.)
In order to demonstrate some of these ideas, I'll present some results that are offshoots of problem that have appeared previously on MSE. To wit,
$$ T(n) = T\left(\frac{n}{2}\right)- 1+\frac{n}{2} + n^2 $$
Thus, $a=1,\ b=2,\ c=[-1,1/2,1],\ k=[0,1,2]$ in the present notation. All of the figures below are in the complex plane. For the first demonstration, we take $b=\varphi^2\approx2.1680$, and imaginary polynomial exponents (i.e., $k\to ik$). The first figure below shows the first 20 values of S(m). It looks like a random mess, until we add the analytical continuation of $T(n),$ call it $T(z)$. This is shown in the second figure below, along with solutions of $T(z)$ for $b=3 \text{ and } \pi$. Everything seems to be natural and well ordered.
In the third figure below, we have taken $m$ or $n$ to lie on the unit circle. On the left, we have $m=e^{i\theta}$ and $n=b^m$, whereas on the right we have $n=e^{i\theta}$ and $m=\log_bn$. Otherwise we have the baseline parameters, except for $k_3=3.5$. The red stars are discrete $S-$values and the blue line is the analytic continuation, $T(z)$.
So, I'm finding here, as with many so-called integer sequences, that there is really no reason to limit the parameters to integers. Your thoughts?
