Linear two-dimensional recurrence relation

Question

As part of my research I have to analyze recurrence relations of the form

$$f_{m,n} = af_{m-1,n} + bf_{m,n-1} + c,$$

where $a,b,c$ are any given real numbers and $f_{m,0}$ and $f_{0,n}$ any given functions (e.g. $f_{m,0} = 2^m$ and $f_{0,n} = n+1$).

Could somebody please suggest some good source (e.g. a website, a book or a paper) I could use to gain insight into this topic? Any hint will be appreciated!

Using generating functions and combinatorical arguments I found that

\begin{align} f_{m,n} &= c\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} \binom{i+j}{i} a^i b^j \\ &\qquad + a^m \sum_{j=0}^{n} \binom{m+j-1}{j} b^j f_{0,n-j} \\ &\qquad + b^n \sum_{i=0}^{m} \binom{n+i-1}{i} a^i f_{m-i,0} \\ &\qquad - a^m b^n \binom{m+n}{m} f_{0,0}. \end{align}

This is nice but not really a closed-form solution.

Thank you very much!

EDIT: For the generating function $F(x,y) = \sum_{m,n \geq 1} f_{m,n} x^m y^n$ I found that

$$F(x,y) = \frac{(1 - ax) F_1(x) + (1 - by) F_2(y) + \frac{cxy}{(1-x)(1-y)} - f_{0,0}}{1-ax-by},$$

where $F_1(x) = \sum_{m \geq 0} f_{m,0} x^m$ and $F_2(y) = \sum_{n \geq 0} f_{0,n} y^n$.

Answer 1

I guess you might not be interested in this but here is a generating function. If $G(x,y)=\sum_{m,n\geq0}f_{m,n}\,x^ny^m$ then $$G(x,y)=\frac{\frac{x^2-(b+2)x}{(1-x)^2}+\frac{1-ay}{1-2y}+\frac{cxy}{(1-x)(1-y)}}{1-ay-bx}.$$

Answer 2

This isn't a full answer, but an attempt to begin to simplify the expression $f_{m,n} = \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} {{i+j}\choose {i,j}} a^i b^j$, as in the comments and in the partial solution in the starting question.

Note that this, too, is a sequence that satisfies the recurrence relation $f_{m,n} = a f_{m-1,n} + b f_{m,n-1} + c$, and has $f_{m,0} = f_{0,n} = 0$ for any $m, n$.

Consider $f'_{m,n} = f_{m,n} - \frac{c}{1 - a - b}$. Then:

$f'_{m,n} = f_{m,n} - \frac{c}{1-a-b} = a f_{m-1,n} + b f_{m,n-1} + c - \frac{c}{1-a-b}\\ = a f'_{m-1,n} + a \frac{c}{1-a-b} + b' f_{m,n-1} + b \frac{c}{1-a-b} + c - \frac{c}{1-a-b} \\= a f'_{m-1,n} + b' f_{m,n-1} + c - (1-a-b) \frac{c}{1-a-b} = a f'_{m-1,n} + b' f_{m,n-1}$

and $f'_{m,0} = f'_{0,n} = -\frac{c}{1-a-b}$. Let $d = -\frac{c}{1-a-b}$. Then this recurrence relation is the same as the original recurrence relation, but with $c = 0$. We can therefore apply your formula to get:

$f'_{m,n} = d a^m \sum_{j = 0}^n {{m+j-1} \choose j} b^j \\ + d b^n \sum_{i = 0}^m {{n+i-1} \choose i} a^i \\ - d$

So in the end, we come down to finding two sums, both of which take the form $\sum_{i = 0}^{n-1} {{k+i-1} \choose i} a^i$.

This is equivalent to finding $\sum_{i = n}^{\infty} {{k+i-1} \choose i} a^i$ (as $\sum_{i = 0}^{\infty} {{k+i - 1} \choose i} a^i = \frac{1}{(1-a)^k}$) in a form that's closed with respect to both $k$ and $n$. I personally doubt that there is a nice expression for this sum except when starting at a fixed $n$.