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



Big-Oh bound of a recursive function with two variables
A simple and exact value of $T(n,m)$ can be computed by the following simple substitution.
$$
C(n+m,m):=\frac{T(n,m)+1}2
$$
Then your recursive function becomes
$$
C(n+m,m)=C(n+m-1,m-1)+C(n+m-1,m)
$$
with the initial condition $C(m,m)=C(m,0)=1$. As you can see, this is the recursive formula for the [binomial coefficient](https://en.wikipedia.org/wiki/Binomial_coefficient) and thus
$$
C(n,m)={{n}\choose{m}}, ~~T(n,m)=2{{n+m}\choose {m}} - 1.
$$


If you use a very loose bound ${n+m\choose m} \le 2^{n+m}$ then you have $T(n,m)=O(2^{n+m})$ as you showed. For better bounds, you may use other inequalities in Wikipedia page.


