My goal is to obtain the Big-Oh bound of the following recursive function with two variables:

$$T(n,m) = T(n, m-1) + T(n-1,m)+1$$

As initial conditions, $T(0,m)=1$ and $T(n, 0)=1$ for $m \geq 0$ and $n \geq 0$, respectively. Then, I think $T(n,m) \in O(2^{n+m})$ which can be proved as follows:

Proof:

• Let's prove $T(n, m) \leq 2 \times 2^{n+m} - 1$ by induction.
  • Base cases: $T(0, m) = 1 \leq 2 \times 2^{m} -1$ and $T(n, 0) = 1 \leq 2 \times 2^{n} -1$ for $n,m \geq 0$
  • Inductive step
    • Assume $T(k, p) \leq 2 \times 2^{k+p} - 1$ for arbitrary $k$ and $p$. Then, there two next steps: $T(k+1, p)$ and $T(k, p+1)$.
    • Case 1) $T(k+1, p) = T(k+1, p-1) + T(k, p) + 1$ by the recursion. Using the above assumption, $T(k+1, p) \leq 2\times 2^{k+p+1} - 1$; thus, $T(k+1, p)$ holds true.
    • Case 2) $T(k, p+1)$ also holds similarly to Case 1.
  • Hence, $T(n, m) \leq 2 \times 2^{n+m} - 1 \in O(2^{n+m})$ .

My questions are

• Are there errors in the above proof?
• Are there tighter bounds than $O(2^{n+m})$?