# two-dimensional recurrence relation

How to solve the following 2D recurrence relation?

$$F(n_1, n_2)=a\bigl[F(n_1-1, n_2)+F(n_1+1, n_2)+F(n_1, n_2-1)+F(n_1, n_2+1)\big]$$ with $$1\leq n_1\leq L_1,\ 1\leq n_2\leq L_2$$. a is a positive real number. Boundary condition: $$F(m_1, m_2)=1$$.

*$$n_1$$ and $$n_2$$ are the coordinate indices and ($$m_1$$, $$m_2$$) is a point in the lattice.

I checked similar questions on this topic and I tried to use the Generating function method as explained Solving two-dimensional recurrence relation $a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$ The difficulty is the boundary condition.

The problem I'm considering is the first passage time of a particle searching for a target in 2-D lattice of size $$L_1 \times L_2$$. Here $$(n_1, n_2)$$ is the position of a particle at time t=0 and $$(m_1, m_2)$$ is the position of the target. $$F(n_1, n_2)=F(n_1, n_2,s)$$ is the Laplace transform (s is the Laplace variable) of the first passage time probability.

• Please use latex conventions. For example $n$ indexed by $1$ is rendered by : dollar sign followed by letter a followed by underscore symbol followed by digit 1 followed by dollar sign. Commented Jun 27, 2017 at 18:06
• I am afraid that there is no other solution than the zero function. Commented Jun 27, 2017 at 18:19
• boundary condition is corrected. Commented Jun 27, 2017 at 22:58
• Hint: find when $\lambda_1^{n_1}\lambda_2^{n_2}$ satisfies the recurrence relation. Linear combinations give the general solution.
– J.G.
Commented Jun 27, 2017 at 22:59
• @J.G. Thanks for your advice. The problem is while there is only one recursion relation, there are two undetermined variables $\lambda_1$ and $\lambda_2$. Commented Jun 28, 2017 at 0:03

Following a suggestion in my comment, we attempt $F=\lambda_1^{n_1}\lambda_2^{n_2}$ so $\frac{1}{a}=\frac{1}{\lambda_1}+\lambda_1+\frac{1}{\lambda_2}+\lambda_2$. Define $\mu_i:=\lambda_i+\frac{1}{\lambda_i}$ so $\lambda_i=\frac{\mu_i\pm\sqrt{\mu_i^2-4}}{2}$ and $\mu_2=\frac{1}{a}-\mu_1$. The most general solution is a linear combination over choices of $\mu_1$, an integral rather than a sum. The result is$$\int_Sd\mu_1\left(a_1^+\left(\mu_1\right)\left(\frac{\mu_1+\sqrt{\mu_1^2-4}}{2}\right)^n+a_1^-\left(\mu_1\right)\left(\frac{\mu_1-\sqrt{\mu_1^2-4}}{2}\right)^n+a_2^+\left(\mu_1\right)\left(\frac{\frac{1}{a}-\mu_1+\sqrt{\left(\frac{1}{a}-\mu_1\right)^2-4}}{2}\right)^n+a_2^-\left(\mu_1\right)\left(\frac{\frac{1}{a}-\mu_1-\sqrt{\left(\frac{1}{a}-\mu_1\right)^2-4}}{2}\right)^n\right)$$for arbitrary functions $a_i^\pm$. The integration range $S$ is an exercise for the reader, and so is finding a solution satisfying the desired boundary condition. It's constrained by the fact that constraints on the $\lambda_i$ constrain the $\mu_i$ (and may in some cases cause one of the values for a $\lambda_i$ consistent with a given $\mu_i$ consistent with that range to be outside it, meaning a coefficient has to be $0$).