Date: Wed, 3 May 95 11:09:11 CDT
From: rusin (Dave Rusin)
To: alsberg@saturn.kj.uib.no
Subject: Re: 2D recurrence problems
Newsgroups: sci.math

In article <3o381g$40h@alf.uib.no> you write:
>Are there any methods for finding closed formulas 
>for 2-d recurrence problems in general? I have an

About as general as 1-d problems.

>example of a recurrence problem that I hope can be turned into
>a closed formula:
>
>F(m,n) = 1/2*F(m-1,n-1) + (v+m+1)*F(m+1,n-1) 
>
>n >= 1,  -n <= m <= n

You mean  n >=0; better, F(m,n)=0 unless n>=0.

>F(0,0)=1;
>F(k,0)=0; k \neq 0

Your recursions makes it clear that  F(m,n) = 0  unless m  and  n  have
the same parity. In that case, define
	H(k,l) = F(k-l, k+l);
we can try to find  H  in general; then  F(m,n) = H((n+m)/2, (n-m)/2)
when  m  and  n  have the same  parity.

I like  H  better than  F  because it's zero outside the first quadrant.
The recurrence here is just
	H(k,l) = (1/2) H(k-1,l) + (v) H(k,l-1) + (k-(l-1)) H(k, l-1).

One possible approach is with power series. As you'll see, this didn't
quite work for me but perhaps the method is instructive.

Let  R(X,Y) = Sum(H(k,l) X^k Y^l).
Then  X*R = Sum( H(k-1,l) X^k Y^l) and similarly for  Y*R;
also  X*Y*dR/dX = Sum( k H(k,l-1) X^k Y^l) 
and Y^2*dR/dY = Sum( (l-1) H(k,l-1) X^k Y^l).
So if we sum (our recurrence relation)*(X^k Y^l), we get the equation
	R = (1/2) X R + (v) Y R + (X Y) dR/dX - Y^2 dR/dY.

You can solve this partial differential equation: let  S = log(R), so
grad(S) = grad(R) / R, and then the equation says
	(XY, -Y^2) . grad(S) = 1 - (1/2) X - v Y.
This is linear in  S. One solution is  S= X/(4Y) + v log(Y), and the solution
to the homogeneous equation is  any function of  XY,  so that  R
must be of the form
	R = U( XY ) * Y^v * exp(X/(4Y)).
for some function  U  of one variable.

The problem here of course is that this  R  does not have a Taylor series
expansion at the origin, so I can't compare coefficients to recover
the sequence  H. What this must mean is that the  H's  are not decaying
fast enough. The usual solution is to determine the rough rate of
growth of  H  and then define  J(k,l)  (say) to be  H(k,l)/(some estimate
of  H). This will give a set of numbers  J  subject to a different relation,
which will lead to a different power series, a different differential
equation, and finally a solution which converges at the origin. But
just offhand I don't see what adjustment to make to  H  to get a good  J.


dave