# 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.

• The special case $k=2$ has an explicit formula, see the OEIS entry and the links therein. – Yuval Filmus Dec 25 '16 at 18:29

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

• Can you please expand on how that would be sufficient to determine $T_k(n)$, maybe with a small example? I don't understand. – skankhunt42 Dec 25 '16 at 19:04
• It follows from all the lemmata. Example, let k=3. We have that T(24 = 3 * 2^3) = 8. Also, T(20 = 3 * 2^3 - 2^2) = T(12 = 3 * 2^3) = 4 and T(21) = 5. Because T(x) - T(x-1) ≤ 1, the values of T(22), T(23) are necessarily 6 and 7. It's easy (but lengthy and boring) to write a closed formula by cases, and similarly easy (but every bit as lengthy and boring) to prove its correctness by Cauchy induction. – quicksort Dec 25 '16 at 19:18

While working through the equalities that quicksort mentioned, I noticed the generalization $T_k(2^n j) = 2^n \text{ for } j \in \{ k \text{..} 2 k-1\}$

Then I calculated some values for k=3:

$2^n j$ = {3..5; 6..10; 12..20; 24..40; 48..80; 96..160}

$T_3(...)$ = {1; 2; 4; 8; 16; 32}.

and I noticed that the groups are separated by just enough numbers for the value to increase by at most 1. This leads to the following algorithm (in python3):

def Tk(k, n):
if n < k:
return 0
if n < 2 * k:
return 1
a = math.floor(math.log(n/k, 2))
end = pow(2, a) * (2*k-1)
if n > end:
return pow(2, a) + (n - end)
return pow(2, a)


The definition leads directly to the (rather) closed formula

$T_k(n) = 0$ for $0 ≤ n < k$

$T_k(n) = 1$ for $k ≤ n < 2k$

$T_k(n) = 2^m$ for $2^mk ≤ n ≤ 2·2^mk-2^m$

$T_k(n) = 2·2^m - j$ for $n = 2·2^mk-j$, $2^m > j ≥ 1$

Proof: Assume n is the smallest counter example and check it gives the result as proposed.