Solving unusual recurrence with two variables

Question

I have the following recurrence relation:

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

With the following base cases (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 want to get a formula for $T(n,0)$. I think that it can be seen that after $i$ iterations we get the following relation:

$T(n,0) = \sum_{j=0}^i {n\choose{j}}\cdot T(n-i,j)$

But I don't know if it helps and can't proceed much further than that.

My question is $-$ what are the right techniques for dealing with recurrence with 2 variables, and in particular with this recurrence (where the second variable is increasing)?

Answer 1

In the cases $C\leq0$ and $C\geq n$ you have $T(n,0)=1$.

Assume that $0<C<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>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.

Answer 2

You know T(n, C) for all n. I’d try to determine T(n, C-1) for all n, then T(n, C-2) and so on.