1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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"? $\endgroup$ – user44191 Apr 5 '17 at 17:24
  • $\begingroup$ 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. $\endgroup$ – Carlos Camino Apr 6 '17 at 9:00
  • $\begingroup$ 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$? $\endgroup$ – Lwins Apr 6 '17 at 12:42
  • $\begingroup$ You are right, thank you! The first term is the one I am trying to simplify right now. $\endgroup$ – Carlos Camino Apr 7 '17 at 13:53
  • $\begingroup$ $\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. $\endgroup$ – user44191 Apr 7 '17 at 18:13
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – Carlos Camino Apr 6 '17 at 9:09
  • $\begingroup$ 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. $\endgroup$ – T. Amdeberhan Apr 6 '17 at 15:42
  • $\begingroup$ 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 :) $\endgroup$ – Carlos Camino Apr 7 '17 at 13:45
1
$\begingroup$

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

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