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.


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

  • $\begingroup$ 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? $\endgroup$ Commented Oct 2, 2020 at 10:55
  • $\begingroup$ 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? $\endgroup$ Commented Oct 2, 2020 at 10:56
  • $\begingroup$ Look, you'll have to do some of it on your own. I showed you the way. You do the rest. $\endgroup$ Commented Oct 2, 2020 at 10:58
  • $\begingroup$ As for your first question, I tested it against an actual implementation, so it seems to work. Perhaps you could figure out why. $\endgroup$ Commented Oct 2, 2020 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.