# Linear two-dimensional recurrence relation

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

• That seems about as closed-form as it can be; it uses the minimal amount of information you can get, and seems to combine terms wherever possible. What more would you be looking for for "closed form"? – user44191 Apr 5 '17 at 17:24
• Perhaps "closed-form solution" is not the right term here. I know from one-dimensional linear recurrence relations (like $f_n = a f_{n-1} + b f_{n-2}$) that their solutions are very simple. I was hoping to be able to make it nicer. Maybe getting rid of the sum signs. – Carlos Camino Apr 6 '17 at 9:00
• It seems that we could hardly simplify the form of your result because that evidently each $f_{0,j}\ (j \leq m)$ and $f_{i,0}\ (i \leq n)$ has to appear at least once in the formula. Maybe we could simplify the first term $c \sum \sum \binom{i+j}{i} a^i b^j$? – Lwins Apr 6 '17 at 12:42
• You are right, thank you! The first term is the one I am trying to simplify right now. – Carlos Camino Apr 7 '17 at 13:53
• $\sum_{j=0}^{n-1} {{i+j}\choose j} b^j$ is the first $n$ terms of $\frac{1}{1-b}^i$; if there is a nice formula for $\sum_{j=n}^\infty {{i+j}\choose i} b^j$, you should be done. – user44191 Apr 7 '17 at 18:13

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

• Thank you for your answer. How did you get that generating function? It looks different to the one I have. Did you use some software? And shouldn't it depend not only on $a$, $b$ and $c$ but also on $f_{m,0}$ and $f_{0,n}$? – Carlos Camino Apr 6 '17 at 9:09
• The $f_{m,0}, f_{0,n}$ contribute to some of the rational functions in the numerator. I got this g.f. manually, you could do it too. – T. Amdeberhan Apr 6 '17 at 15:42
• I see! You used the two examples $f_{m,0} = 2^m$ and $f_{0,n} = n+1$ from above. I added the general g.f. I found back then to the question. Looks pretty similar :) – Carlos Camino Apr 7 '17 at 13:45

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