How fast does this two dimensional recursion grow?

Question

The recursion

$$T[2n,2m]=a+T[2n,2m-2]+T[2n-2,2m-2]$$ where $T[\ell,0]=0$ at any $\ell\in\mathbb N$ and $a\in\mathbb N_{>0}$ is fixed grows exponentially. However what is the precise growth rate?

Answer 1

If for some $m$ $T[2n,2m] = C_m$ are independent of $n$ then $T[2n,2m + 2] = a + 2 C_m = C_{m+1}$ is also constant. $C_0 = 0$, so your recursion relation is just $C_{m+1}=a+2C_m = a \sum\limits^{m-1}_{i=0}2^i= a(2^{m}-1)$.

Answer 2

For convenience, I am dropping all the factors $2$ and writing the recurrence as

$$T[n+1,m+1]=a+T[n+1,m]+T[n,m].$$

From this

$$T[l,0]=0$$

$$T[l+1,1]=a+0+0=a$$

$$T[l+2,2]=a+a+a=3a$$

$$T[l+3,3]=a+3a+3a=7a$$

$$\cdots$$

$$T[l+k,k]=a+2T[l+k-1,k-1]=(2^k-1)\,a.$$

The other values remain unknown.