Proof of recurrence relation, using induction

Question

Been working on this for some time now but I can't get past the last step. Any hints are appreciated.

So I have this recurrence relation of:

T(n, m) = 2 for $n,m = 0$

T(n, m) = T(n-1, m) + T(n, m-1) + 2 for $n,m \gt 0$

Now I am supposed to prove that:

T(n, n) $\ge 2^n$

Here is what I have so far:

Base Case:

When n = 0, T(0, 0) $\ge 2^0$

LHS: 2, RHS: 1 True

When n = 1, T(1, 1) $\ge 2^1$

LHS: 6, RHS: 2 True

Inductive Hypothesis:

Assume for some arbitrary value 'k' that the statement T(k, k) $\ge 2^k$

Inductive Step:

Prove if the statement in the inductive hypothesis is true, then it must be true for T(k+1, k+1) $\ge 2^{k+1}$

T(k+1, k+1) = T((k+1)-1, k+1) + T(k+1, (k+1)-1) + 2

T(k+1, k+1) = T(k, k+1) + T(k+1, k) + 2

I don't know what to do after this step since there are 2 variables inside T and they have different values

Answer 1

Since

$$T(n,k)=T(n,k-1)+T(n-1,k)\tag{1}$$

for $n,k\ge 1$, and $T(0,k)=T(n,0)=2$ for $n,k\ge 0$, a fairly easy induction argument, which for now I’ll leave to you, shows that $T(n,k)>0$ for $n,k\ge 0$. But then $(1)$ implies that $T(n,k)>T(n,k-1)$ and $T(n,k)>T(n-1,k)$ for $n,k\ge 1$, and therefore

$$\begin{align*} T(n,n)&=T(n,n-1)+T(n-1,n)\\ &>T(n-1,n-1)+T(n-1,n-1)\\ &=2T(n-1,n-1)\,. \end{align*}$$

Since $T(0,0)=2>2^0$, the desired inequality now follows by induction on $n$.