Solving recurrence relation in 2 variables We already know how to solve a homogeneous recurrence relation in one variable using characteristic equation. Does a similar technique exists for solving a homogeneous recurrence relation in 2 variables. More formally, How can we solve a homogeneous recurrence relation in 2 variables? For example,
F(n,m) = F(n-1,m) + F(n,m-1)

Given some initial conditions, how can we solve the above recurrence relation?

Use generating functions like the one variable case, but with a bit of extra care. Define:
$$
G(x, y) = \sum_{r, s \ge 0} F(r, s) x^r y^s
$$
Write your recurrence so there aren't subtractions in indices:
$$
F(r + 1, s + 1) = F(r + 1, s) + F(r, s + 1)
$$
Multiply by $x^r y^s$, sum over $r \ge 0$ and $s \ge 0$. Recognize e.g.:
\begin{align}
\sum_{r, s \ge 0} F(r + 1, s) x^r y^s
  &= \frac{1}{x} \left( G(x, y) - \sum_{s \ge 0} F(0, s) y^s \right) \\
  &= \frac{G(x, y) - G(0, y)}{x} \\
\sum_{r, s \ge 0} F(r + 1, s + 1) x^r y^s
  &= \frac{1}{x} \left( 
                   G(x, y) 
                     - \sum_{s \ge 0} F(0, s) y^s
                     - \sum_{r \ge 0} F(r, 0) x^s
                     + F(0, 0)
                 \right) \\
  &= \frac{G(x, y) - G(0, y) - G(x, 0) + F(0, 0)}{x y}
\end{align}
Here $G(0, y)$ and $G(x, 0)$ are boundary conditions. If you are lucky, the resulting equation can be solved for $G(x, y)$.
In the specific case of binomial coefficients, you have $F(r, 0) = F(0, r) = 1$, so that $G(x, 0) = \frac{1}{1 - x}$ and $G(0, y) = \frac{1}{1 - y}$:
$$
\frac{G(x, y) - 1 / (1 - y) - 1 / (1 - x) + 1}{x y}
  = \frac{G(x, y) - 1 / (1 - y)}{x}  + \frac{G(x, y) - 1 / (1 - x)}{y}
$$
The result is:
\begin{align}
G(x, y) &= \frac{1}{1 - x - y} \\
        &= \sum_{n \ge 0} (x + y)^n
\end{align}
This is:
$$
[x^r y^s] G(x, y) = \binom{r + s}{r} = \binom{r + s}{s}
$$
as expected.
