# Recurrence Relation with two variables

I am trying to solve the following recurrence relation:

$T(a,b)=T(a-2^{b-1}+1,b) + T(a,b-1)$ where: $$T(a,-1)=0\\T(0,0)=0\\T(a,1)=1\\T(a,0)=1$$

I tried using Matlab and Wolfarmalpha however they don't accept recurrences with more than one variable.

Can someone give me a hint or point me in the right direction?

• What's $l$ in the recurrence? – user58697 Mar 13 '14 at 5:58
• sorry the $l$ is a typing error. I corrected the equation. – kyloc Mar 13 '14 at 14:18
• Something is still wrong here. Setting $b=1$ results in $T(a,1) = T(a, 1) + 1$ – user58697 Mar 13 '14 at 17:32
• We can assume that T(a,1)=1 – kyloc Mar 13 '14 at 22:13
• We can never express any $T(a,2)$ as a sum of only $T(*,-1), T(*,0), T(*,1)$ values. The $b=2$ never goes away, and has no explicit definitions. You need a $b$-reducing formula. – Neil W Mar 14 '14 at 0:43

OK. An immediate desire is to plug in $b = 2$:

$$T(a,2) = T(a - 1, 2) + T(a, 1) = T(a-1, 2) + 1$$

so $T(a, 2) = a+1$. Next step is to plug in $b=3$:

$$T(a, 3) = T(a - 3, 3) + T(a,2) = T(a-3, 3) + (a+1)$$

Notice the arithmetic progression here. So, assuming that $T == 0$ for all negative $b$ (not just $-1$), $T(a, 3) \approx Ca^2$.

Inductively, we may conclude that $T(a, b) \approx C(b)a^{b-1}$. I have to admit that I am too lazy to estimate $C$.

I guess you can take it from here.

• Just out of curiosity, which algorithm complexity you're trying to estimate? – user58697 Mar 14 '14 at 6:43