# Proof of recurrence relation, using induction

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

• First try to find $T(m,0)$ and $T(0,n)$. And use the recurrence relation repeatedly.
– QED
Oct 12, 2020 at 20:27
• Please write an informative and searchable title... one that actually refers to the specific content of your problem. Oct 12, 2020 at 20:28
• @QED Both T(m, 0) and T(0, n) would equal to 2 but how will that help my case because I have to prove T(n, n) Oct 12, 2020 at 20:31

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