Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You might be intrested in cellular automatons and number triangles. –  mick Oct 2 '12 at 21:20
    
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. –  mick Oct 2 '12 at 21:23
    
@mick For the current question we can safely assume that the recursion is a simple linear recursion with no constants. –  gibraltar Oct 3 '12 at 5:06
    
You might be intrested in en.wikipedia.org/wiki/Master_theorem –  mick Oct 3 '12 at 12:37
    
Can you apply the master theorem to multi-variable recurrences? –  jmite Aug 14 '13 at 21:58

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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