Binomial upper bound for the bi-color Ramsey numbers (Erdős-Szekeres)

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)$.

The inequality $R(r,s) \leq R(r,s-1)+R(r-1,s)$ has been proven in @Harshal's post, and is explained in many different entries online. My difficulty was in the transition from the inequality to the binomial formulation:

$$ {\displaystyle R(r,s)\leq R(r,s-1)+R(r-1,s)\leq {\binom {r+s-3}{r-1}}+{\binom {r+s-3}{r-2}}={\binom {r+s-2}{r-1}}}$$

This is my attempt in the absence of any answers explicitly explaining this combinatorial upper bound:

By symmetry, $R(r,s)=R(s,r),$ which justifies only considering Ramsey numbers where $r>s$ in $R(r,s)$ without loss of generality. Likewise the so-called base cases $R(r,1)=1$ and $R(r,2)=r$ are readily accessible in many online posts to need further consideration. In particular $R(r,1)=1$ almost appears axiomatic:

As a base case, observe that $r(k, 1) = 1$ for all $k.$ Indeed, in any two-coloring of the edges of $K_1$ (of which there are none), we will always find a (trivial) blue $K_1.$

To bring out an intuition leading to the proof of the formula in question, let me pick an example that is manageable in size, such as $R(5,4),$ and apply recursively the inequality until reaching either $R(m,1)$ or $R(1,m),$ and hence ending up with an expression in which each element contributes $1$ to the value of $R(r,s).$ To make the expressions more compact, $R(r,s)=rs:$

$\begin{align} \small R(r,s)&\leq R(r,s-1)+R(r-1,s)\\ &\leq \color{red}{53} + \color{blue}{44}\\ &\leq \color{red}{52+43}+ \color{blue}{43+ 34}\\ &\leq \color{red}{51+42+42+33}+ \color{blue}{42+33+ 33+24}\\ &\leq\small\color{red}{51+41+32+41+32+32+23}+ \\ &\small\quad\;\color{blue}{41+32+32+23+32+23+23+14}\\ &\leq\Tiny\color{red}{51+41+31+22+41+31+22+31+22+22+13}+ \\ &\Tiny\quad\;\color{blue}{41+31+22+31+22+22+13+31+22+22+13+22+13+14}\\ &\leq\Tiny\color{red}{51+41+31+21+12+41+31+21+12+31+21+12+21+12+13}+\\ &\Tiny\quad\;\color{blue}{41+31+21+12+31+21+12+21+12+13+31+21+12+21+12+13+21+12+13+14}\\ &= 35 \end{align}$

Evidently, there is overlap in the patterns below certain nodes in the recursive expression that are reached through different paths. For example, notice the repetitive pattern beyond $42:$

$$\begin{align} &51+\color{orange}{42}+\color{red}{42}+33+ \color{magenta}{42}+33+ 33+24\\ &\leq\small51+\color{orange}{41+32}+\color{red}{41+32}+32+23+ \\ &\small\quad\;\color{magenta}{41+32}+32+23+32+23+23+14\\ &\leq\Tiny{51+\color{orange}{41+31+21+12}+\color{red}{41+31+21+12}+31+21+12+21+12+13}+\\ &\Tiny\quad\;\color{magenta}{41+31+21+12}+31+21+12+21+12+13+31+21+12+21+12+13+21+12+13+14 \end{align}$$

These entries do indeed represent overlapping paths that can be better visualized as follows:

Many paths are taken multiple times, and each one adds $1$ to the total sum (in red at the margins).

In this way counting the different paths is just a matter of counting the possible trajectories heading right (East) and left (West), but always South. For instance, the $\color{red}6$ different ways of getting to $31$ are

Notice that they all go through $32$ - after that there are zero degrees of freedom.

To calculate the number of paths is straightforward noticing that the number of ways to get to a node is given by Pascal's triangle:

So at this point all that remains is summing these coefficients along diagonal lines of Pascal's triangle. To this end, the sum of some values along a diagonal of Pascal's triangle from left and up to right and low is immediately available in the line below. For example the sum of $4$ terms along the third diagonal is:

$$\binom{2}{0}+\binom{3}{1}+\binom{4}{2}+\binom{5}{3}=\binom{6}{3}$$

Hence we are adding along the row number $R=3$ of Pascal's triangle $N=4$ values, and we can generalize as

$$\small\binom{R-1}{0}+\binom{R-1+1}{1}+\binom{R-1+2}{2}+\cdots+\binom{R-1+N-1}{N-1}=\binom{R+N-2}{N-1}\tag 1$$

This happens to be the $R(r-1,s)$ part of the inequality for $R(5,4)$ because we are adding along the $s-2$ diagonal of Pascal's triangle with $s=4.$ This is apparent in the diagrams above, where the elements along a diagonal reduce the first entry, keeping the second constant. We want to add along that diagonal exactly $r-1$ elements, which in the example correspond to $5-1=4.$

From $(1)$ it is clear that the sum of these binomials can be calculated directly from Pascal's triangle as

$$\binom{(s-2)+r-1}{(r-1)-1}=\binom{r+s-3}{r-2}$$

To this we have to add the sum along the diagonal in the opposite direction: from right and up to left and down to account for $\binom{3}{3}+\binom{4}{3}+\binom{5}{3},$ corresponding to the $R(r,s-1)$ part of the inequality, but the answer now is also on the row below of Pascal's triangle, but just one step more to the right:

$$\binom{(s-2)+r-1}{r-1}=\binom{r+s-3}{r-1}$$

This can also be seen by symmetry in the diagram below:

And thus,

$$ {\displaystyle R(r,s)\leq R(r,s-1)+R(r-1,s)= {\binom {r+s-3}{r-1}}+{\binom {r+s-3}{r-2}}={\binom {r+s-2}{r-1}}}\tag*{$\blacksquare$}$$

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.