Difficult reccurence with two variables
It will be less confusing to reparametrize $T$ by switching the order in which the second parameter increases:
$$
T(n,k) =
\begin{cases}
1 &amp; \text{if } n \leq C \text{ or } k = 0, \\
T(n-1,k) + T(n-m,k-1) &amp; \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 &gt; m$ and $k &gt; 0$. Then
\begin{align}
T(n,k) &amp;= T(n-m,k-1) + T(n-1,k) \\ &amp;=
T(n-m,k-1) + T(n-m-1,k-1) + T(n-2,k) \\ &amp;=
T(n-m,k-1) + \cdots + T(2-m,k-1) + T(1,k) \\ &amp;=
T(n-m,k-1) + \cdots + T(2-m,k-1) + 1 \\ &amp;=
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 &gt; 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 &gt; 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.