0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ First try to find $T(m,0)$ and $T(0,n)$. And use the recurrence relation repeatedly. $\endgroup$
    – QED
    Oct 12, 2020 at 20:27
  • 1
    $\begingroup$ Please write an informative and searchable title... one that actually refers to the specific content of your problem. $\endgroup$ Oct 12, 2020 at 20:28
  • $\begingroup$ @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) $\endgroup$ Oct 12, 2020 at 20:31

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.