41
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ You might be intrested in cellular automatons and number triangles. $\endgroup$
    – mick
    Oct 2, 2012 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, 2012 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, 2012 at 5:06
  • 1
    $\begingroup$ You might be intrested in en.wikipedia.org/wiki/Master_theorem $\endgroup$
    – mick
    Oct 3, 2012 at 12:37
  • 1
    $\begingroup$ Can you apply the master theorem to multi-variable recurrences? $\endgroup$
    – jmite
    Aug 14, 2013 at 21:58

3 Answers 3

38
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Is any CAS software able to solve it automatically? $\endgroup$
    – skan
    Dec 10, 2017 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$ Jan 25, 2021 at 13:18
13
$\begingroup$

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.

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

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}$

$\endgroup$

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.