Difficult reccurence with two variables

Question

My question is a follow-up for the following thread: Solving unusual recurrence with two variables

I baisically have the same reccurence relation but with a small change---

$$T(n,k) = T(n-1,k)+T(n-m,k+1)$$

The change is the addition of $m$ in the second element in the recursion (instead of 1 in the original question)

The boundary cases remain the same (for some given constant $C$):

For all $x \leq C$ and for any $k$: $T(x,k)=1$

For all $y \geq C$ and for any $n$: $T(n,y)=1$

I'm trying to approximate the value of $T(n,0)$ (with a tight upper bound as possible). In the original question we were able to give a close formula for the reccurence after $i$ steps, which helped bounding its value. But due to the addition of $m$, this formula doesn't hold anymore.

A direction for how to address such reccursions or any idea for the solution would be very helpful.

Answer 1

It will be less confusing to reparametrize $T$ by switching the order in which the second parameter increases: $$ T(n,k) = \begin{cases} 1 & \text{if } n \leq C \text{ or } k = 0, \\ T(n-1,k) + T(n-m,k-1) & \text{otherwise}. \end{cases} $$

Having done this switch, let us get rid of $C$ completely. Including $C$ as the third parameter, notice that $T(n+C,k,C) = T(n+D,k,D)$, and so it suffices to solve the recurrence for some value of $C$. We choose $C = 1$.

Let us now unroll the recurrence. Suppose that $n > m$ and $k > 0$. Then \begin{align} T(n,k) &= T(n-m,k-1) + T(n-1,k) \\ &= T(n-m,k-1) + T(n-m-1,k-1) + T(n-2,k) \\ &= T(n-m,k-1) + \cdots + T(2-m,k-1) + T(1,k) \\ &= T(n-m,k-1) + \cdots + T(2-m,k-1) + 1 \\ &= T(n-m,k-1) + \cdots + T(2,k-1) + m + 1. \end{align} This gives us $T(n,1) = n-m-1+m+1 = n$ if $n > m$; you can check that the same formula works for all $n \geq 1$. Continuing, $$ T(n,2) = T(n-m,1) + \cdots + T(2,1) + m + 1. $$ If $n > m$ then we can compute exactly $$ T(n,2) = (n-m) + \cdots + (2) + m + 1 = \frac{(n-m)(n-m+1)}{2} + m. $$ When $1 \leq n \leq m$, you can check that $T(n,2) = n$.

At this point we can in principle continue and obtain exact formulas. However, they will be quite messy. Fortunately, when $m$ is constant, it is easy to prove by induction that $T(n,k) = \Theta(n^k)$; indeed, $T(n,k) = n^k/k! + O(n^{k-1})$. Obtaining an explicit dependence on $m$ is certainly possible, but unless it's expressly needed, I wouldn't bother.