# Difficult reccurence with two variables

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.

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.
• Thanks! I just don't sure about the part where the equation is unrolled to $T(2-m,k-1)$, how did we get $2-m$ and what if it isn't defined? Commented Oct 2, 2020 at 10:55
• Also, a dependency in $m$ would be very helpful, does it required to define the equation for $(n,k,m)$? If so, let's assume that the boundary case is $T(n,k,1) = 1$. To complicate this a little more, what if we also assume that $C=O(m)$ Is it still solvable with the same aaproach? Commented Oct 2, 2020 at 10:56