Solving unusual recurrence with two variables
In the cases $C\leq0$ and $C\geq n$ you have $T(n,0)=1$.
Assume that $0&lt;C&lt;n$. Show that
$$T(n,0)=\sum_{i=0}^{\color{red}{k}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$
for $0\leq k\leq n-C$ and $n\leq 2C$. It looks like this is the formula that you mentioned in the question, except that the binomial coefficient should have the same amount that is being subtracted from the first entry of $T$.
Apply it for $k=n-C$.
We get $$T(n,0)=\sum_{i=0}^{n-C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{n-C}\binom{n-C}{i}=2^{n-C}$$
If $n&gt;2C$ the formula that we get is
$$T(n,0)=\sum_{i=0}^{\color{red}{C}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$
Putting $k=n-C$ we get
$$T(n,0)=\sum_{i=0}^{C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{C}\binom{n-C}{i}\in O(n^C)$$
since it is a polynomial of degree $C$.

We didn't need it this time, but a technique that could be useful to work with recurrences is generating functions.