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?

  • $\begingroup$ You might be intrested in cellular automatons and number triangles. $\endgroup$ – mick Oct 2 '12 at 21:20
  • $\begingroup$ If im not mistaken if your recursion contains no minus , division , root or logaritm then F(n,n) is usually expressible in closed form. If not then by adding the concept of superfunctions it increases the probability alot. $\endgroup$ – mick Oct 2 '12 at 21:23
  • $\begingroup$ @mick For the current question we can safely assume that the recursion is a simple linear recursion with no constants. $\endgroup$ – gibraltar Oct 3 '12 at 5:06
  • $\begingroup$ You might be intrested in en.wikipedia.org/wiki/Master_theorem $\endgroup$ – mick Oct 3 '12 at 12:37
  • 1
    $\begingroup$ Can you apply the master theorem to multi-variable recurrences? $\endgroup$ – jmite Aug 14 '13 at 21:58

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.

  • 2
    $\begingroup$ Is any CAS software able to solve it automatically? $\endgroup$ – skan Dec 10 '17 at 20:29
  • $\begingroup$ Can you recommend a textbook, technical note or paper where this method is explained in more detail. What materials did you use when learning this? $\endgroup$ – nilo de roock Jan 25 at 13:18

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.

  • 2
    $\begingroup$ That's a great answer. Did you figure out yourself or it's on the books? $\endgroup$ – skan Mar 11 '17 at 19:10
  • 1
    $\begingroup$ My own derivartion. $\endgroup$ – vonbrand May 30 '18 at 13:42
  • $\begingroup$ @skan That means he refuses to share his sources. $\endgroup$ – nilo de roock Jan 25 at 13:20

You will need to specify $F(0,r)$ and $F(s,0)$ as initial conditions. Your recurrence is precisely that for Pascal's triangle. If you specify $F(0,r)=F(s,0)=1$ you will have $F(n,m)={n+m \choose n}$. You can use linearity to turn it into a sum over initial conditions and binomial coefficients. If your initial condition is $F(1,0)=1, F(r,0)=F(0,s)=0$ you will get a Pascal's triangle shifted down to the left by one slot, so $F(m,n)={m+n-1 \choose m-1}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.