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?

You can use generating functions, as we did in the single variable case.

Let $G(x,y)=\sum_{m,n\ge 0}F(n,m) x^n y^m$. We'll express $G$ in a nice form from which one can recover $F(n,m)$.

As you didn't specify initial conditions, let $$H_1(x)=\sum_{n\ge0} F(n,0)x^n, H_2(y)=\sum_{m\ge0} F(0,m)y^m, c=F(0,0)$$

By the recurrence of $G$, if we multiply it by $1-x-y$, most of the terms will cancel. I'll elaborate on that.

I choose $1-x-y$ in a similar manner to that of constructing the characteristic polynomial in one variable: $1$ corresponds to $F(n,m)$, $x$ to $F(n-1,m)$ and $y$ to $F(n,m-1)$, i.e. $F(n-a,m-b)$ is replaced by $x^ay^b$.

$$G(x,y)(1-x-y)=\sum_{m,n\ge 0}F(n,m) (x^n y^m-x^{n+1}y^m-x^{n}y^{m+1})=$$ We'll group coefficients of the same monomial: $$\sum_{m,n \ge 1} (F(n,m)-F(n-1,m)-F(n,m-1)) x^{n}y^{m}+$$ $$\sum_{n \ge 1} (F(n,0)-F(n-1,0)) x^{n}+\sum_{m \ge 1} (F(0,m)-F(0,m-1)) y^{m}+F(0,0)=$$ $$H_1(x)(1-x) + H_2(y)(1-y)-c$$

So, finally, $$G(x,y) = \frac{H_1(x)(1-x) + H_2(y)(1-y)-c}{1-x-y}$$ (Compare this to the relation $Fib(x)=\frac{x}{1-x-x^2}$ where $Fib$ is the generating function of the Fibonacci sequence.)

How do we recover $F$? We use the formal identity $\frac{1}{1-x-y}=\sum_{i\ge 0}(x+y)^i$. Let $S(x,y)=H_1(x)(1-x) + H_2(y)(1-y)-c=\sum_{n,m} s_{n,m} x^ny^m$. It gives us: $$G(x,y) = \sum_{i \ge 0}S(x,y)(x+y)^i = \sum_{n,m \ge 0} (\sum_{a,b \ge 0}s_{a,b} \binom{n+m-a-b}{n-a})x^ny^m$$ So $F(n,m) = \sum_{a,b \ge 0}s_{a,b} \binom{n+m-a-b}{n-a}$. I have an hidden assumption - that $S$ is a polynomial! Otherwise convergence becomes an issue.

I guess that your initial conditions are $F(n,0)=1, F(0,m) = \delta_{m,0}$, which give $S(x,y)=1$, so $F(n,m)=\binom{n+m}{n}$.

EDIT: In the general case, where $F(n,m)=\sum_{a,b} c_{a,b}F(n-a,m-b)$ where the sum is over finitely many tuples in $\mathbb{N}^{2} -\setminus \{ (0,0) \}$, the generating function will be of the form $\frac{H(x,y)}{1-\sum_{a,b} c_{a,b}x^a y^b}$ where $H$ depends on the initial conditions.

When we had one variable, we wrote $\frac{q(x)}{1-\sum a_i x^i} =\sum \frac{q_i(x)}{1-r_i x}$ where $r_i^{-1}$ is a root of $1-\sum a_i x^i$ and used $\frac{1}{1-cx} = \sum c^ix^i$.

With 2 variables, this is not always possible, but we can write $\frac{1}{1-\sum_{a,b} c_{a,b}x^a y^b}=\sum_{i \ge 0} (\sum_{a,b} c_{a,b}x^a y^b)^{i}$ and use the binomial theorem to expand. We can also use complex analysis methods to derive asymptotics of $F(n,m)$ from the generating functions.

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.