Binomial upper bound for the bi-color Ramsey numbers (Erdős-Szekeres) 
The question: How did Erdös - Szekeres came up with a close form with a binomial for the upper bound: Where does the idea behind $R(2,2)=\binom{2+2-2}{2-1}$ -  I do see that $R(2,2)=2$ - or $\binom{s+t-3}{s-1}\left(\text{or }\binom{s+t-3}{s-2}\right)$ come from? And how is the induction over $s$ and $t$ work?
What I understand:

*

*I see that $R(s,t) \leq R(s-1,t)+R(s,t-1)$

*I understand that ${\displaystyle  {\binom {r+s-3}{r-2}}+{\binom {r+s-3}{r-1}}={\binom {r+s-2}{r-1}}}$ - Pascal's triangle.

*I also see that $\forall s, t ∈ \mathbb N,$ the relationship $R(s, t) = R(t, s)$ holds.

*And I get it that $R(s,2)=R(2,s)=s.$
The problem: There are tons of sites where the proof of the inequality above is readily available, including one of the answers to this post. However, when the inequality is proven, the binomial formula seems to appear out of thin air like it is self-evident, typically with a short justification such as: easily proven by induction on $s$ and $t.$ But how does this work? How did they come up with this binomial to begin with? This binomial coefficient appears before testing the base cases.


Background info:
For instance, in here:
Since $R(r, s) ≤ R(r − 1, s) + R(r, s − 1)$ so this automatically gives an upper bound, although not in the closed form that we expect.
The closed form expression is ${\displaystyle R(r,s)\leq {\binom {r+s-2}{r-1}}}.$ To derive this use double induction on $r$ and $s.$ The base case $r = s = 2$ is easily established as $${\displaystyle R(2,2)=2\leq {\binom {2+2-2}{2-1}}=2}.$$
Now assume the expression holds for $R(r − 1, s)$ and $R(r, s − 1).$ Then
$${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1)\leq {\binom {r+s-3}{r-2}}+{\binom {r+s-3}{r-1}}={\binom {r+s-2}{r-1}}}$$ gives us our upper bound. Note that we have used Pascal's relation in the last equivalence.
But why did they start already applying the binomial formula they intend to prove in ${\displaystyle R(2,2)=2\leq {\binom {2+2-2}{2-1}}=2},$ and how does the inductive process proceed from that point?

I see there are related questions, and in fact, I have tried to contribute with a possible answer as to the proof of a finite Ramsey number for every combination of two natural numbers here to get feedback.
However, I still have problems with the immediately related proof of the inequality (theorem of Erdős-Szekeres):
$$R(s,t) \leq \binom{s+t-2}{s-1}$$
as in here:

I see that this inequality is fulfilled by the base cases, as well as $s+t<5,$ but I presume other inequalities could also be fulfilled by the first Ramsey numbers.

In the following two answers that I found online it seems as though the Ramsey number on, say $(r,t),$ i.e. $R(r,t)$ is somewhat just replaced by $r$ and $t$ in the combinatorics solution. So I don't get the analogy to Pascal's triangle...
Solution 1:
The answer can be found here:
$$R(k,l) \leq \binom{k+l-2}{k-1}$$
because the recurrence $$R(k,l) \leq R(k-1,l) + R(k,l-1) $$ can be seen as the paths from a point $R(k,l)$ on the grid below to $(1,1):$

and the number of ways to get to a point on a lattice $(x,y)$ taking off from $(0,0)$ are:
$$\binom{x+y}{x}$$
Here we are moving in the opposite direction, and stopping at $(1,1),$ which reduces the count to:
$$\binom{(x-1)+(y-1)}{x-1}=\binom{x+y-2}{x-1}$$

"We’ve placed the value $1$ at each position $(k, 1)$ or $(1, l)$ in this grid, corresponding to the
base case $r(k, 1) = r(1, l) = 1$ of our induction. At the point $(k, l)$ in the grid, we know
that the value $r(k, l)$ at that point is upper-bounded by the sum of the values immediately
below and immediately to the left. Applying this same recurrence to these adjacent nodes,
we see that every left/down path from $(k, l)$ to the boundary will contribute $1$ in the final
sum (corresponding to the value $1$ at the boundary points). Thus, $r(k, l)$ is upper-bounded
by the number of left/down paths to the boundary, which is in turn equal to the number of
left/down paths from $(k, l)$ to $(1, 1),$ which is exactly
$\binom{k+l-2}{k-1}."$

Solution 2:
From here:


 A: Note: This answer uses the following terminology:
$r=$number of friends and $s=$number of non friends.
I want to prove that $R(r,s) \le R(r-1,s)+R(r,s-1)$
(using an interpretation in English which might give some insight)
For this, I need to show that there will exist either:
i) group of $r$ mutual friends or
ii) group of $s$ mutual non friends
in a group of $R(r-1,s) + R(r,s-1)$ people.
Suppose this group had you with $R(r-1,s) + R(r,s-1)-1$ other people.
You would have some friends, some non friends. Let's call these two groups F and NF.
I claim that either of the two happen (from Pigeonhole principle):
a) $|F| \ge R(r-1,s)$ or $|NF|\ge R(r,s-1)$
b) $|NF| \ge R(r-1,s)$ or $|F|\ge R(r,s-1)$ 
Because if this isn't the case then  $|F|+|NF|\le (R(r-1,s)-1) + (R(r,s-1)-1) = (R(r-1,s)+R(r,s-1)-2)$.
But since we started with $R(r-1,s) + R(r,s-1)-1$ other people, this is a contradiction.
If, (a) is true, then you already have a group of $s$ friends!
So, lets analyse (b).
In (b) you have 2 cases:

Case 1: if $|F| \ge R(r-1,s)$
This means that amongst your friends there was a group of $r-1$ mutual friends.
Hence, when I include you, I create a group of $r$ friends.
Case 2: $|NF|\ge R(r,s-1)$
This means that amongst your non friends there was a group of $s-1$ people who didn't know each other.
Hence, when I include you, I create a group of $s$ non friends.
Thus, in a group of $R(r-1,s) + R(r,s-1)$ people, there will either be a group of $r$ mutual friends or a group of $s$ mutual non friends. So, $R(r,s) \le R(r-1,s)+R(r,s-1)$.
A: To see the upper bound, you are closest with your solution 1.
We have:
$$R(r,b)\le R(r-1,b) + R(r,b-1)$$
(I am using $r$ for red and $b$ for blue - I find it easier to remember!).
Using the idea of Pascal's triangle, we can extend this into:
$$R(r,b)\le  \left(R(r-2,b) + R(r-1,b-1)\right) + \left(R(r-1,b-1) + R(r,b-2)\right)$$
or:
$$R(r,b)\le  R(r-2,b) + 2R(r-1,b-1) + R(r,b-2)$$
The step takes us to:
$$R(r-3,b)+3R(r-2,b-1)+3R(r-1,b-2)+R(r,b-3)$$
with the next step involving $1,4,6,4,1$, and continue using binomial coefficients, except where we hit the boundaries at $R(1,b)=R(r,1)=1$ and then $R(0,b)=R(r,0)=0$, and this leaves the binomial in question.
From Known Ramsey numbers, you can see the pattern by looking at the anti-diagonals.
A: If you are only familiar with inducting on a single variable $n$, here's how this can be rewritten, ala comment by Andreas Blass.

Boundary Lemma: $\forall s, t: R(1,t), R(s,1)$ both $\le {s+t -2 \choose s-1}$

Proof: "every graph contains a clique of size $1$" (quoted from OP first image).  Note that this is in a sense not part of the later induction on single $n$ (the way I wrote it).  But IMHO it is more natural to think of the entire boundary as base cases.

Hypothesis $H(n)$ for $n\ge 4$: $\forall s > 1, t> 1,$ with $s+t=n: R(s,t) \le {s+t -2 \choose s-1}$

We will prove by induction on $n$ that $H(n)$ is valid $\forall n \ge 4$.

Base case $H(4)$: i.e. $s=t=2$

Proof: See the $R(2,2)$ case in the OP "Theorem 3.3".

Induction case: proving that $H(n-1) \implies H(n)$ 

Proof: consider any $s>1, t>1, s+t=n$.  We have $R(s,t) \le R(s-1,t) + R(s,t-1)$.  


*

*Case A: $s-1 >1$.  In this case, $R(s-1,t) \le {s + t - 3 \choose s-2}$ by $H(n-1)$ because $(s-1) + t = n-1$


*

*Lemme expand this since this is where you're having trouble.  $H(n-1)$ says $\forall a>1, b>1, a+b=n-1: R(a,b) \le {a+b-2 \choose a-1}$.  Now we substitute $a=s-1, b=t$ and check: Yes they do satisfy $a>1$ (because we're analyzing Case A where $s-1>1$) and $b=t>1$ and finally also $a+b=n-1$.  So by $H(n-1)$ we have $R(a,b) = R(s-1,t) \le {a+b-2 \choose a-1} = {s + t - 3 \choose s-2}$.


*Case B:  $s-1 = 1$.  In this case, $R(s-1,t) \le {s + t - 3 \choose s-2}$ by Boundary Lemma.  (The induction hypothesis $H(n-1)$ is irrelevant here.)

*Conclusion: $R(s-1,t) \le {s + t - 3 \choose s-2}$ whether $s-1 > 1$ or $=1$.

*Similarly, $R(s,t-1) \le {s+t - 3 \choose s-1}$, whether $t-1 > 1$ (by induction) or $t-1=1$ (by Boundary Lemma)
Therefore, for any $s>1, t>1, s+t=n$ we have $R(s,t) \le {s + t - 3 \choose s-2} + {s + t - 3 \choose s-1} \le {s+t -2 \choose s-1}$.  This proves $H(n)$.

Hopefully this helps?  Or am I just repeating the same confusion by the quoted authors.  
In general, I don't think one needs to be so explicit.  You can induct on several integer variables at once as long as you know that the recurrence eventually reach boundary cases which you prove separately (in this case, via the Boundary Lemma).
Note that you do need to prove the boundary cases.  E.g. if you only proved the $R(1,1)$ case and then use this recurrence, it will not work, because e.g. $R(3,2) \le R(3,1) + R(2,2)$ and you have no info on what happens at $R(3,1)$.  And this is why I prove all the boundary cases in one swoop, and also why even though the boundary is not technically the base case for $H(n)$ (the way I wrote it), IMHO it is natural to think of the entire boundary as base cases.
