Solving a bivariate recurrence equation
Repeated substitution

Repeatedly substitute in, and look for a pattern:

$$\begin{align*}
T(m,n) &amp;= T(m/2,n/2) + T(m, n/2) + 1\\
&amp;= T(m/4,n/4) + 2 T(m/2,n/4) + T(m, n/4) + 3\\
&amp;= T(m/8,n/8) + 3 T(m/4,n/8) + 3 T(m/2,n/8) + T(m, n/8) + 7\\
&amp;\vdots\\
\end{align*}$$

Do you see the pattern?  The coefficients $1,3,3,1$ should remind you of binomial coefficients.  The pattern is

$$T(m,n) = 2^k-1 + \sum_{i=0}^k {k \choose i} T(m/2^i, n/2^k).$$

You can prove that this holds for all $k$ (by induction on $k$).  Then, setting $k=\lg n$, we find

$$T(m,n) = n-1 + \sum_{i=0}^{\lg n} {\lg n \choose i} T(m/2^i, 1).$$

So it suffices to know how to evaluate $T(m,1)$ for all $m$.  That information cannot be deduced from the recurrence you gave us -- it needs to be supplied as additional base cases.

For instance, suppose we are given the base cases $T(m,1) = 1$ for all $m$.  Then we find

$$T(m,n) = n-1 + \sum_{i=0}^{\lg n} {\lg n \choose i} = 2n-1 = \Theta(n).$$

However, if we were given different base cases, the solution might be different.

Guess-and-check

Another approach is to somehow guess the solution (for instance, by playing with a bunch of examples and looking for patterns), and then check that it holds.  For your example, if we assume $T(m,n) = T(m/2,n/2) + T(m,n/2) + 1$ and we assume $T(m,1)=1$ for all $m$, then rubbing our rabbit's foot for luck, we might get lucky and guess

$$T(m,n) = 2n-1.$$

It is then easy to plug in and confirm that this is a valid solution to the recurrence you gave.

However, in general, guess-and-check is often very hard -- you can try many guesses, but sometimes it can be very difficult to find a guess that turns out to be correct.