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