Solving recurrence $T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$

I am currently solving a problem that I have reduced to computing the following function efficiently.

$$T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$$

The base cases are $\forall n < k: T_k(n) = 0$ and $\forall k \leq n < 2k: T_k(n) = 1$ Note: $n$ and $k$ are non-negative integers.

I need to compute this function for multiple values of $k$ and $n$.

I can compute this function in $\theta(n)$ by a simple recursive function using just the definition and speed up the computation by using memoization. However, this isn't fast enough and I was wondering if there is a closed form expression for it and can be computed in $o(n)$.

I have no idea how to solve this recurrence.

Observe that $T_k(2^n k) = 2^n$. Furthermore, it is easy to see that either $T_k(\alpha) = T_k(\alpha-1)$ or $T_k(\alpha) = 1+T_k(\alpha-1)$. Using the previous two results, it can also be shown that $T_k(2^n k - 2^{n-1}) = T_k(2^{n-1} k)$.

Now, consider
$$\delta_k(n) = T_k(2^n k - 2^{n-1} + 1) - T_k(2^n k - 2^{n-1} )$$

It should be easy to prove by induction that for all $k, n$ it holds that $\delta_k(n) = 1$. This should be sufficient to uniquely determine the value of $T_k(n)$ for all $n$.

StackExchange Computer Science Q#67881, answer score: 2