How to find the solution of $T(n,m) = T((n-1),m) + T(n,(m-1))$ in terms of big $O$ notation? I would like to solve the recurrence $T(n,m) = T((n-1),m) + T(n,(m-1))$.
I think the solution is $$O(2^{n+m})$$ because in every step you can reduce either $n$ or $m$ by one or not, but I can not really come up with a proper mathematical argument for this.
 A: We can obtain the solution explicitly using generating functions. Define $$G_n (t):= \sum_{m=0}^{\infty}T_{n,m}t^m,$$
and now multiply the recurrence by $t^m$ and sum:
$$\sum_{m=1}^{\infty}T_{n,m} t^m=\sum_{m=1}^{\infty}T_{n-1,m} t^m+\sum_{m=1}^{\infty}T_{n,m-1} t^m.$$
We sum from $m=1$ because otherwise we the $T_{n,m-1}$ would give us $T_{n,-1}$ for $m=0$. All in all we have $$G_n(t)-T_{n,0}=G_{n-1}(t)-T_{n-1,0}+ t\cdot G_n(t),$$
and now some initial values would come in handy! I'll assume that $T_{n,0}=0$ for all $n$ if you don't mind!. This gives a recurrence relation for the functions:  $$G_n(t)=\frac{1}{1-t}G_{n-1}(t)$$ and just iterate to find $G_n(t)=(\frac{1}{1-t})^n G_{0}(t)$. Again, we're missing initial conditions badly, but $T_{0,m}=1$ for all $m$, just so that $$G_0(t)=0+\sum_{m=1}^{\infty} 1\cdot t^m=\frac{t}{1-t}$$
for |t|<1. It's a generating function, we don't really care for convergence, and note that our previous constraint that all $T_{n,0}=0$ left us with no choice but to say that $T_{0,0}=0$, I think?
Altogether we expand $G_n(t)$ into a binomial series to get:
$$G_n(t)=\left(\frac{1}{1-t}\right)^n \frac{t}{1-t}=\frac{t}{(1-t)^{(n+1)}}=t\cdot \sum_{m=0}^{\infty} {m+n\choose m}\cdot t^m,$$
which means $$T_{n,m}={n+m-1\choose m}.$$ And in fact Mathematica confirms that it satisfies the recurrence!
A: Looking at this as a sum in reverse, suppose that our "base value" is at $T(1,1)$.  To get to $T(n,m)$, follow Pascal's Triangle, since $T(n,m)=T(n-1,m)+T(n,m-1)$, exactly matching the definition of Pascal's Triangle.  Therefore, we have
$$T(n,m)=T(n-1,m)+T(n,m-1)={n+m-1\choose m}T(1,1)$$
This is a bit tricky, but if you notice that $n$ and $m$ are equidistant from $n+m\over 2$, then it is clear that we have ${n+m-1\choose m}={n+m-1\choose n}$, so the formula isn't actually "biased" towards $n$ or $m$, even though it looks that way.  The $-1$ means that we get $T(1,1)=\binom 11T(1,1)$ as we would expect...
A: It's faster than $O(2^{n+m})$ - note that if $n=1$, time complexity is $O(m)$, not $O(2^m)$.
I don't see the exact answer, but I do see good lower and upper bounds:
$O(2^{min(m,n)}) \leq O(T) \leq O(2^{n+m})$
Think of a binary tree generated by $T$. First node has parameters $(m,n)$, and it has two children $(m-1,n)$ and $(m,n-1)$, and so on. A node has one (or zero) children iff one (or both) of its arguments are zero.
Note that minimum length of a leaf-to-root path is $min(m,n)$ and maximum is $m+n$. Therefore total number of nodes is between $2^{min(m,n)}$ and $2^{n+m}$. Can anybody improve it?..
PS Usually this kind of problems are solved using dynamic programming, which reduces complexity to polynomial.
