How to get a recurrence relation from an expression with maximum There is a certain function $F(r,s)$ (where $r\geq -1$ and $s\geq 0$ are integers) that satisfies the following relation:
$$
\max\big[2 F(r,s) - F(r-1,s) - F(r-1,s-1)~~~,~~~F(r+1,s+1) - F(r-1,s)\big] =  0
\\
F(r,0)=1 ~~~~~ \forall r\geq 0
\\
F(0,s)=0 ~~~~~ \forall s\geq 1
\\
F(-1,s)=0 ~~~~~ \forall s\geq 0
$$
Is there a way to get from this relation, an explicit recurrence relation on $F(r,s)$, so that I can numerically compute e.g. $F(1000,1000)$?
NOTE: I had a similar function $G(r,s)$ that satisfies the following similar relation:
$$
\max\big[2 G(r,s) - G(r-1,s) - G(r-1,s-1)~~~,~~~G(r,s) - G(r-2,s-1)\big] =  0
\\
G(r,0)=1 ~~~~~ \forall r\geq 0
\\
G(0,s)=0 ~~~~~ \forall s\geq 1
\\
G(-1,s)=0 ~~~~~ \forall s\geq 0
$$
Here I managed to find the solution myself. There are two cases: either the leftmost term is larger, and then $G(r,s)=[G(r-1,s) - G(r-1,s-1)]/2$, or the rightmost term is larger, and then $G(r,s)=G(r-2,s-1)$. Therefore, the recurrence relation is:
$$
G(r,s) = \min\big[ 
[G(r-1,s) - G(r-1,s-1)]/2
~~~,~~~
G(r-2,s-1)
\big]
$$
From this relation and the boundary conditions, it is easy to compute $G(1000,1000)$.
But, this does not work with $F$. How can I get a recurrence relation on $F$?
 A: You can bootstrap the recursion and see if you find a pattern. The easiest way to read this post is by drawing a 2x2 grid and taking notes in it.
Your expression is:
$$\max\left\{ 2 F(r,s) - F(r-1,s) - F(r-1,s-1), \quad F(r+1,s+1) - F(r-1,s)\right\} =  0$$
Due to the argument $s-1$, you cannot fill in $s=0$. Since $F(r-1,s)$ occurs in both terms, you can take it out of the max expression:
$$\max\left\{ 2 F(r,s) - F(r-1,s-1), \quad F(r+1,s+1)\right\} =  F(r-1,s) \qquad (1)$$
For $r=0$ and $s \geq 1$, (1) means:
$$\max\left\{ 0, F(1,s+1)\right\} =  0$$
so $F(1,s+1) \leq 0$.
For $r=1$ and $s \geq 1$, (1) means:
$$\max\left\{ 2 F(1,s) - F(0,s-1), \quad F(2,s+1)\right\} =  0,$$
so $F(2,s) \leq 0$ and $2 F(1,s) \leq F(0,s-1)$, with equality for at least one of them.
For $s=1$ and $r \geq 1$, (1) means:
$$\max\left\{ 2 F(r,1) - 1, \quad F(r+1,2)\right\} =  F(r-1,1),$$
so $F(r,1)\leq0.5+0.5F(r-1,1)$ and $F(r+1,2)\leq F(r-1,1)$, with equality for at least one of them
There is no pattern that arises, but
$$F(r,s)=\begin{cases}1 & \text{if } r\geq 0 \text{ and } s=0\\ 0 & \text{otherwise}\end{cases}$$
satisifies the recursion.
