Mixing
How to get a recurrence relation from an expression with maximum
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
There is a certain function $F(r,s)$ (where $rgeq -1$ and $sgeq 0$ are integers) that satisfies the following relation:
$$
maxbig[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 rgeq 0
\
F(0,s)=0 ~~~~~ forall sgeq 1
\
F(-1,s)=0 ~~~~~ forall sgeq 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:
$$
maxbig[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 rgeq 0
\
G(0,s)=0 ~~~~~ forall sgeq 1
\
G(-1,s)=0 ~~~~~ forall sgeq 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) = minbig[
[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$?
recurrence-relations maxima-minima
asked Jul 24 at 18:55
Erel Segal-Halevi
4,10811757
 |Â
show 4 more comments
up vote
4
down vote
favorite
There is a certain function $F(r,s)$ (where $rgeq -1$ and $sgeq 0$ are integers) that satisfies the following relation:
$$
maxbig[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 rgeq 0
\
F(0,s)=0 ~~~~~ forall sgeq 1
\
F(-1,s)=0 ~~~~~ forall sgeq 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:
$$
maxbig[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 rgeq 0
\
G(0,s)=0 ~~~~~ forall sgeq 1
\
G(-1,s)=0 ~~~~~ forall sgeq 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) = minbig[
[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$?
recurrence-relations maxima-minima
asked Jul 24 at 18:55
Erel Segal-Halevi
4,10811757
Do you mean $r,s$ integers, or $r,s$ non negative integers?
– san
Aug 1 at 2:04
It is not clear to me how the case you mention for $G$ is handled. In order the recurrence to work, you need the values of $G(1,s)$ for all $s$, and there are restrictions on these values.
– san
Aug 1 at 4:25
@san I see what you mean - another row of $r$ is needed because of the $r-2$. I added the row where $r=-1$.
– Erel Segal-Halevi
Aug 1 at 8:14
It is also not clear if for example $(r,s)=(0,0)$ satisfies the relation. The relation implies that $F(r+1,s+1)−F(r−1,s)le 0$, which makes sense for $(r,s)=(0,0)$, but $2F(r,s)−F(r−1,s)−F(r−1,s−1)$ is not defined, so the maximum is not defined.
– san
Aug 1 at 20:41
1
The previous case you solved has a unique solution. However, with the new recursion formula there are multiple solutions (assuming the condition of my previous comments). For example, the function G is a solution (it satisfies the recursion formula), but also $F(r,s)=G(r-1,s)$ is a solution. I'm pretty sure that you can vary the parameter t=F(2,1) freely between 1/2 (first solution F=G) and 0 (the second solution), but I haven't done the full computations. Moreover, you can also vary other entries of F. What can be proven is that F(r,s)=0 for $rle s-1$ if $rge 1$ and $(r,s)$ is not $(2,1)$.
– san
Aug 1 at 21:07
 |Â
show 4 more comments
up vote
4
down vote
favorite
up vote
4
down vote
favorite
There is a certain function $F(r,s)$ (where $rgeq -1$ and $sgeq 0$ are integers) that satisfies the following relation:
$$
maxbig[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 rgeq 0
\
F(0,s)=0 ~~~~~ forall sgeq 1
\
F(-1,s)=0 ~~~~~ forall sgeq 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:
$$
maxbig[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 rgeq 0
\
G(0,s)=0 ~~~~~ forall sgeq 1
\
G(-1,s)=0 ~~~~~ forall sgeq 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) = minbig[
[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$?
recurrence-relations maxima-minima
asked Jul 24 at 18:55
Erel Segal-Halevi
4,10811757
There is a certain function $F(r,s)$ (where $rgeq -1$ and $sgeq 0$ are integers) that satisfies the following relation:
$$
maxbig[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 rgeq 0
\
F(0,s)=0 ~~~~~ forall sgeq 1
\
F(-1,s)=0 ~~~~~ forall sgeq 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:
$$
maxbig[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 rgeq 0
\
G(0,s)=0 ~~~~~ forall sgeq 1
\
G(-1,s)=0 ~~~~~ forall sgeq 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) = minbig[
[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$?
recurrence-relations maxima-minima
asked Jul 24 at 18:55
Erel Segal-Halevi
4,10811757
edited Aug 1 at 8:13
asked Jul 24 at 18:55
Erel Segal-Halevi
4,10811757
asked Jul 24 at 18:55
Erel Segal-Halevi
4,10811757
asked Jul 24 at 18:55
Erel Segal-Halevi
4,10811757
4,10811757
Do you mean $r,s$ integers, or $r,s$ non negative integers?
– san
Aug 1 at 2:04
It is not clear to me how the case you mention for $G$ is handled. In order the recurrence to work, you need the values of $G(1,s)$ for all $s$, and there are restrictions on these values.
– san
Aug 1 at 4:25
@san I see what you mean - another row of $r$ is needed because of the $r-2$. I added the row where $r=-1$.
– Erel Segal-Halevi
Aug 1 at 8:14
It is also not clear if for example $(r,s)=(0,0)$ satisfies the relation. The relation implies that $F(r+1,s+1)−F(r−1,s)le 0$, which makes sense for $(r,s)=(0,0)$, but $2F(r,s)−F(r−1,s)−F(r−1,s−1)$ is not defined, so the maximum is not defined.
– san
Aug 1 at 20:41
1
The previous case you solved has a unique solution. However, with the new recursion formula there are multiple solutions (assuming the condition of my previous comments). For example, the function G is a solution (it satisfies the recursion formula), but also $F(r,s)=G(r-1,s)$ is a solution. I'm pretty sure that you can vary the parameter t=F(2,1) freely between 1/2 (first solution F=G) and 0 (the second solution), but I haven't done the full computations. Moreover, you can also vary other entries of F. What can be proven is that F(r,s)=0 for $rle s-1$ if $rge 1$ and $(r,s)$ is not $(2,1)$.
– san
Aug 1 at 21:07
 |Â
show 4 more comments
Do you mean $r,s$ integers, or $r,s$ non negative integers?
– san
Aug 1 at 2:04
It is not clear to me how the case you mention for $G$ is handled. In order the recurrence to work, you need the values of $G(1,s)$ for all $s$, and there are restrictions on these values.
– san
Aug 1 at 4:25
@san I see what you mean - another row of $r$ is needed because of the $r-2$. I added the row where $r=-1$.
– Erel Segal-Halevi
Aug 1 at 8:14
It is also not clear if for example $(r,s)=(0,0)$ satisfies the relation. The relation implies that $F(r+1,s+1)−F(r−1,s)le 0$, which makes sense for $(r,s)=(0,0)$, but $2F(r,s)−F(r−1,s)−F(r−1,s−1)$ is not defined, so the maximum is not defined.
– san
Aug 1 at 20:41
1
The previous case you solved has a unique solution. However, with the new recursion formula there are multiple solutions (assuming the condition of my previous comments). For example, the function G is a solution (it satisfies the recursion formula), but also $F(r,s)=G(r-1,s)$ is a solution. I'm pretty sure that you can vary the parameter t=F(2,1) freely between 1/2 (first solution F=G) and 0 (the second solution), but I haven't done the full computations. Moreover, you can also vary other entries of F. What can be proven is that F(r,s)=0 for $rle s-1$ if $rge 1$ and $(r,s)$ is not $(2,1)$.
– san
Aug 1 at 21:07
Do you mean $r,s$ integers, or $r,s$ non negative integers?
– san
Aug 1 at 2:04
Do you mean $r,s$ integers, or $r,s$ non negative integers?
– san
Aug 1 at 2:04
It is not clear to me how the case you mention for $G$ is handled. In order the recurrence to work, you need the values of $G(1,s)$ for all $s$, and there are restrictions on these values.
– san
Aug 1 at 4:25
It is not clear to me how the case you mention for $G$ is handled. In order the recurrence to work, you need the values of $G(1,s)$ for all $s$, and there are restrictions on these values.
– san
Aug 1 at 4:25
@san I see what you mean - another row of $r$ is needed because of the $r-2$. I added the row where $r=-1$.
– Erel Segal-Halevi
Aug 1 at 8:14
@san I see what you mean - another row of $r$ is needed because of the $r-2$. I added the row where $r=-1$.
– Erel Segal-Halevi
Aug 1 at 8:14
It is also not clear if for example $(r,s)=(0,0)$ satisfies the relation. The relation implies that $F(r+1,s+1)−F(r−1,s)le 0$, which makes sense for $(r,s)=(0,0)$, but $2F(r,s)−F(r−1,s)−F(r−1,s−1)$ is not defined, so the maximum is not defined.
– san
Aug 1 at 20:41
It is also not clear if for example $(r,s)=(0,0)$ satisfies the relation. The relation implies that $F(r+1,s+1)−F(r−1,s)le 0$, which makes sense for $(r,s)=(0,0)$, but $2F(r,s)−F(r−1,s)−F(r−1,s−1)$ is not defined, so the maximum is not defined.
– san
Aug 1 at 20:41
1
1
The previous case you solved has a unique solution. However, with the new recursion formula there are multiple solutions (assuming the condition of my previous comments). For example, the function G is a solution (it satisfies the recursion formula), but also $F(r,s)=G(r-1,s)$ is a solution. I'm pretty sure that you can vary the parameter t=F(2,1) freely between 1/2 (first solution F=G) and 0 (the second solution), but I haven't done the full computations. Moreover, you can also vary other entries of F. What can be proven is that F(r,s)=0 for $rle s-1$ if $rge 1$ and $(r,s)$ is not $(2,1)$.
– san
Aug 1 at 21:07
The previous case you solved has a unique solution. However, with the new recursion formula there are multiple solutions (assuming the condition of my previous comments). For example, the function G is a solution (it satisfies the recursion formula), but also $F(r,s)=G(r-1,s)$ is a solution. I'm pretty sure that you can vary the parameter t=F(2,1) freely between 1/2 (first solution F=G) and 0 (the second solution), but I haven't done the full computations. Moreover, you can also vary other entries of F. What can be proven is that F(r,s)=0 for $rle s-1$ if $rge 1$ and $(r,s)$ is not $(2,1)$.
– san
Aug 1 at 21:07
 |Â
show 4 more comments
1 Answer
1
active
oldest
votes
up vote
2
down vote
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:
$$maxleft 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:
$$maxleft 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:
$$maxleft 0, F(1,s+1)right = 0$$
so $F(1,s+1) leq 0$.
For $r=1$ and $s geq 1$, (1) means:
$$maxleft 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:
$$maxleft 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)=begincases1 & textif rgeq 0 text and s=0\ 0 & textotherwiseendcases$$
satisifies the recursion.
answered Aug 1 at 19:46
LinAlg
5,4111319
Indeed there is a trivial solution that I did not notice. Thanks!
– Erel Segal-Halevi
Aug 3 at 10:33
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
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:
$$maxleft 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:
$$maxleft 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:
$$maxleft 0, F(1,s+1)right = 0$$
so $F(1,s+1) leq 0$.
For $r=1$ and $s geq 1$, (1) means:
$$maxleft 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:
$$maxleft 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)=begincases1 & textif rgeq 0 text and s=0\ 0 & textotherwiseendcases$$
satisifies the recursion.
answered Aug 1 at 19:46
LinAlg
5,4111319
Indeed there is a trivial solution that I did not notice. Thanks!
– Erel Segal-Halevi
Aug 3 at 10:33
add a comment |Â
up vote
2
down vote
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:
$$maxleft 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:
$$maxleft 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:
$$maxleft 0, F(1,s+1)right = 0$$
so $F(1,s+1) leq 0$.
For $r=1$ and $s geq 1$, (1) means:
$$maxleft 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:
$$maxleft 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)=begincases1 & textif rgeq 0 text and s=0\ 0 & textotherwiseendcases$$
satisifies the recursion.
answered Aug 1 at 19:46
LinAlg
5,4111319
Indeed there is a trivial solution that I did not notice. Thanks!
– Erel Segal-Halevi
Aug 3 at 10:33
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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:
$$maxleft 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:
$$maxleft 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:
$$maxleft 0, F(1,s+1)right = 0$$
so $F(1,s+1) leq 0$.
For $r=1$ and $s geq 1$, (1) means:
$$maxleft 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:
$$maxleft 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)=begincases1 & textif rgeq 0 text and s=0\ 0 & textotherwiseendcases$$
satisifies the recursion.
answered Aug 1 at 19:46
LinAlg
5,4111319
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:
$$maxleft 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:
$$maxleft 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:
$$maxleft 0, F(1,s+1)right = 0$$
so $F(1,s+1) leq 0$.
For $r=1$ and $s geq 1$, (1) means:
$$maxleft 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:
$$maxleft 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)=begincases1 & textif rgeq 0 text and s=0\ 0 & textotherwiseendcases$$
satisifies the recursion.
answered Aug 1 at 19:46
LinAlg
5,4111319
answered Aug 1 at 19:46
LinAlg
5,4111319
answered Aug 1 at 19:46
LinAlg
5,4111319
answered Aug 1 at 19:46
LinAlg
5,4111319
5,4111319
Indeed there is a trivial solution that I did not notice. Thanks!
– Erel Segal-Halevi
Aug 3 at 10:33
add a comment |Â
Indeed there is a trivial solution that I did not notice. Thanks!
– Erel Segal-Halevi
Aug 3 at 10:33
Indeed there is a trivial solution that I did not notice. Thanks!
– Erel Segal-Halevi
Aug 3 at 10:33
Indeed there is a trivial solution that I did not notice. Thanks!
– Erel Segal-Halevi
Aug 3 at 10:33
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861656%2fhow-to-get-a-recurrence-relation-from-an-expression-with-maximum%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Do you mean $r,s$ integers, or $r,s$ non negative integers?
– san
Aug 1 at 2:04
It is not clear to me how the case you mention for $G$ is handled. In order the recurrence to work, you need the values of $G(1,s)$ for all $s$, and there are restrictions on these values.
– san
Aug 1 at 4:25
@san I see what you mean - another row of $r$ is needed because of the $r-2$. I added the row where $r=-1$.
– Erel Segal-Halevi
Aug 1 at 8:14
It is also not clear if for example $(r,s)=(0,0)$ satisfies the relation. The relation implies that $F(r+1,s+1)−F(r−1,s)le 0$, which makes sense for $(r,s)=(0,0)$, but $2F(r,s)−F(r−1,s)−F(r−1,s−1)$ is not defined, so the maximum is not defined.
– san
Aug 1 at 20:41
1
The previous case you solved has a unique solution. However, with the new recursion formula there are multiple solutions (assuming the condition of my previous comments). For example, the function G is a solution (it satisfies the recursion formula), but also $F(r,s)=G(r-1,s)$ is a solution. I'm pretty sure that you can vary the parameter t=F(2,1) freely between 1/2 (first solution F=G) and 0 (the second solution), but I haven't done the full computations. Moreover, you can also vary other entries of F. What can be proven is that F(r,s)=0 for $rle s-1$ if $rge 1$ and $(r,s)$ is not $(2,1)$.
– san
Aug 1 at 21:07