Solve $\sum_{k=0}^\infty T_{k/2}x^k$

Question

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

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

2. 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?

Answer 1

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)$.

Answer 2

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. :-)