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})$?