How to solve a recurrence relation with two variables

Question

I have the following recurrence relations

$$ \phi(i,j) = {1\over 4}\left( \phi(i-1,j) + \phi(i+1,j) + \phi(i, j-1) + \phi(i, j+1) \right) $$

for

$$ i=1,\cdots, N-1, \,\text{and}\, j=1,\cdots , M-1 $$

with the initial conditions:

$$ \begin{align*} \phi(0, j) &= a \\ \phi(N, j) &= b \\ \phi(i, 0) & = c \\ \phi(i, M) &= d \\ \end{align*} $$

where intially $\phi = \phi_0 = \text{const}$ for the interior points.

Where

• $n, m, N, M \in \mathbb N $,
• $a, b, c, d \in \mathbb R $

I am trying to find a closed-form for this relation (that is an explicit expression for $\phi(i, j)$). I have only very basic knowledge about linear recurrence relation problems only. Unfortunately, in this, I have no idea how to start.

I appreciate any help.

Answer 1

Focusing on an example with $N = 5, M = 4$ and making the formulations we obtain the set of equations

$$ \left\{ \begin{array}{c} -a-c+4 \phi _{1,1}-\phi _{1,2}-\phi _{2,1}=0 \\ -c-\phi _{1,1}+4 \phi _{1,2}-\phi _{1,3}-\phi _{2,2}=0 \\ -b-c-\phi _{1,2}+4 \phi _{1,3}-\phi _{2,3} =0\\ -a-\phi _{1,1}+4 \phi _{2,1}-\phi _{2,2}-\phi _{3,1}=0 \\ -\phi _{1,2}-\phi _{2,1}+4 \phi _{2,2}-\phi _{2,3}-\phi _{3,2}=0 \\ -b-\phi _{1,3}-\phi _{2,2}+4 \phi _{2,3}-\phi _{3,3} =0\\ -a-\phi _{2,1}+4 \phi _{3,1}-\phi _{3,2}-\phi _{4,1} =0\\ -\phi _{2,2}-\phi _{3,1}+4 \phi _{3,2}-\phi _{3,3}-\phi _{4,2}=0 \\ -b-\phi _{2,3}-\phi _{3,2}+4 \phi _{3,3}-\phi _{4,3}=0 \\ -a-d-\phi _{3,1}+4 \phi _{4,1}-\phi _{4,2}=0\\ -d-\phi _{3,2}-\phi _{4,1}+4 \phi _{4,2}-\phi _{4,3} =0\\ -b-d-\phi _{3,3}-\phi _{4,2}+4 \phi _{4,3}=0 \\ \end{array} \right. $$

thus generating the linear system

$M\phi = B$ with

$$ M = \left( \begin{array}{cccccccccccc} 4 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 4 & 1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & 4 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 4 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & -1 & 4 & -1 & 0 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 & -1 & 4 & 0 & 0 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 & 0 & 4 & -1 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & -1 & 0 & -1 & 4 & -1 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 4 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 4 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 4 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 4 \\ \end{array} \right),\ \ \ B = \left( \begin{array}{c} a+c \\ c \\ b+c \\ a \\ 0 \\ b \\ a \\ 0 \\ b \\ a+d \\ d \\ b+d \\ \end{array} \right) $$

and

$$ \phi = \left\{\phi _{1,1},\phi _{1,2},\phi _{1,3},\phi _{2,1},\phi _{2,2},\phi _{2,3},\phi _{3,1},\phi _{3,2},\phi _{3,3},\phi _{4,1},\phi _{4,2},\phi _{4,3}\right\} $$

Making now $a=-1,b=1,c=1,d=-1$ we obtain fot $N=40, M=50$ the solution represented as follows

Follows a MATHEMATICA script which generates the graphics.

Remove["Global`*"]
n = 40;
m = 50;
equ[i_, j_] := 4 Subscript[phi, i, j] - ( Subscript[phi, i - 1, j] + Subscript[phi, i + 1, j] + Subscript[phi, i, j - 1] + Subscript[phi, i, j + 1])
equs = Flatten[Table[equ[i, j], {i, 1, n - 1}, {j, 1, m - 1}]];
Phi = Table[Subscript[phi, i, j], {i, 0, n}, {j, 0, m}];
For[i = 0, i <= n, i++, Subscript[phi, i, 0] = a; Subscript[phi, i, m] = b];
For[j = 1, j <= m, j++, Subscript[phi, 0, j] = c; Subscript[phi, n, j] = d];
vars = Flatten[Take[Phi, {2, n}, {2, m}]];
B = equs /. Thread[vars -> 0];
M = Grad[equs, vars];
parms = {a -> -1, b -> 1, c -> 1, d -> -1};
B0 = B /. parms;
solphi = LinearSolve[M, -B0];
MatrixPlot[Phi /. parms /. Thread[vars -> solphi]]

NOTE

With the characteristic function technique we could start as follows.

Calling

$$ S(x,y) = \sum _{j=0}^m \left(\sum _{i=0}^n x^i y^j a_{i,j}\right) $$

and having in mind

$$ \sum _{j=0}^m \left(\sum _{i=1}^n x^i y^j a_{i-1,j}\right)=x \left(\sum _{j=0}^m \left(\sum _{i=0}^n x^i y^j a_{i,j}\right)-\sum _{j=0}^m y^j x^n a_{n,j}\right)\\ \sum _{j=0}^m \left(\sum _{i=0}^{n-1} x^i y^j a_{i+1,j}\right)=\frac 1x\left(\sum _{j=0}^m \left(\sum _{i=0}^n x^i y^j a_{i,j}\right)-\sum _{j=0}^m y^j a_{0,j}\right)\\ \sum _{j=1}^m \left(\sum _{i=0}^n x^i y^j a_{i,j-1}\right)=y \left(\sum _{j=0}^m \left(\sum _{i=0}^n x^i y^j a_{i,j}\right)-\sum _{i=0}^n x^i y^m a_{i,m}\right)\\ \sum _{j=0}^{m-1} \left(\sum _{i=0}^n x^i y^j a_{i,j+1}\right)=\frac 1y\left(\sum _{j=0}^m \left(\sum _{i=0}^n x^i y^j a_{i,j}\right)-\sum _{i=0}^n x^i a_{i,0}\right) $$

we can find

$$ S(x,y) = \frac{x y}{x^2y+x y^2-4x y+x+y}\left(\left(a x^{n+1}+\frac bx\right)\sum_{j=0}^m y^j+\left(c y^{m+1}+\frac dy\right)\sum _{i=0}^n x^i\right) $$

Answer 2

We can redefine $\phi(i,j)$ as $\varphi((M+1)i+j)$ to get the new recurrence:

$$4\varphi(n)=\varphi(n-M-1)+\varphi(n-1)+\varphi(n+1)+\varphi(n+M+1)$$

with initial conditions given by

$$\varphi(j)=a,~\varphi((M+1)N+j)=b,~\varphi((M+1)i)=c,~\varphi((M+1)i+M)=d$$

and $\varphi(n)=0$ at the "corners", where we restrict $j\le M$ and $i\le N$.

This can then be tackled as you would a one-dimensional linear recurrence using matrices.