1
$\begingroup$

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)?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks that looks good. Can you please explain why you're applying $k=n-C$? $\endgroup$ – Ofir Gordon Aug 25 '20 at 6:57
  • 1
    $\begingroup$ @OfirGordon You can see it in the second-to-last equation. The purpose is to get to the boundary conditions $T(C,i)=1$. $\endgroup$ – plop Aug 25 '20 at 11:32
  • $\begingroup$ @polp. Another thing, when placing $k=n-C$ you ignore the other possible boundary condition - $T(n,0)=1$. If $n-k>>C$ than the equation will converge must faster, giving a tighter bound. Is it possible to take the other condition into consideraion as well? $\endgroup$ – Ofir Gordon Aug 26 '20 at 11:26
  • $\begingroup$ @OfirGordon That's right. For $n>2C$ there are terms in the formula in which the second entry is larger than $C$. Those are equal to $1$ and don't continue to be expanded. $\endgroup$ – plop Aug 26 '20 at 11:53
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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