Solve $\sum_{k=0}^\infty T_{k/2}x^k$ I'm trying to find a generating function ($g(x) = \sum_{k=0}^\infty T_{k}x^k$) from a recursion.
The problem is that I found a term that I've never seen before and I don't know how to proceed:
$$\sum_{k=0}^\infty T_{k/2}x^k$$
$$
T(n) =
\begin{cases}
const  & \text{if $n < 2$} \\
n + 2T(n/2) + const & \text{otherwise}  \\
\end{cases}
$$

More details


*

*By "proceed" I mean something like $\sum_{k=1}^\infty T_k x^t = g(x) - T_0$.

*I tried with the substitution $k=2t$. I get $\sum_{t=0}^\infty T_{t}x^{2t} = \sum_{t=0}^\infty(T_tx^t)(1x^t)$ … but then?
 A: If by $\sum T_{k/2} x^k$ you mean $\sum T_k x^{2k}$, then this is $\sum T_k (x^2)^k = g(x^2)$.
A: Another interpretation is that $T(n/2)$ actually means $T(\lfloor n/2 \rfloor)$. In that case, your recurrence (slightly rewritten for explicitness on the constants)
$$
T(n) =
\begin{cases}
c_0 & \text{if $n = 0$} \\
c_1 & \text{if $n = 1$} \\
n + 2T(\lfloor n/2 \rfloor) + c_2 & \text{if $n \ge 2$}  \\
\end{cases}
$$
would give the generating function
$$g(z) = \sum_n T(n)z^n = c_0 + c_1z + \sum_n (n + 2T(\lfloor n/2 \rfloor) + c_2) z^n$$
so we have 
$$g(z) - (c_0 + c_1z + \sum_n nz^n + \sum_n c_2 z^n) = \sum_n 2T(\lfloor n/2 \rfloor)z^n$$
This last sum is the same as $$(1 + z)\sum_k 2 T(k) z^{2k},$$ because for each $k$, we want $T(k)$ to be counted both in the term $2T(k)z^{2k}$ and in the term $2T(k)z^{2k+1}$. And $\sum_k T(k)z^{2k}$ is of course $g(z^2)$ as Antonio Vargas shows in his answer.
Altogether, you have:
$$
g(z) = c_0 + c_1z + \frac{z}{(1-z)^2} + \frac{c_2}{1-z} + (1+z)g(z^2)
$$
Tell me if you manage to solve that. :-)
