[proofplan]
The bound is proved by induction on $s + t$. The base cases $R(s, 2) = s$ and $R(2, t) = t$ are immediate from the definition and match the binomial at the boundary. The inductive step combines the standard recurrence $R(s, t) \leq R(s - 1, t) + R(s, t - 1)$ — which is the $r = 2$ case of the [Existence of r-Set Ramsey Numbers](/theorems/2050) — with Pascal's identity $\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}$, exactly matching the binomial recurrence. The diagonal consequence $R(s) \leq 4^s$ then follows from the central-binomial estimate $\binom{2m}{m} \leq 4^m$, which is itself a short argument from the binomial theorem.
[/proofplan]
[step:Verify the base cases of the induction]
We induct on $s + t$ with $s, t \geq 2$. The smallest value is $s + t = 4$, achieved only at $(s, t) = (2, 2)$.
*Case $(s, t) = (2, 2)$.* Any 2-colouring of $K_2$ has a single edge, which is monochromatic. Hence $R(2, 2) = 2 = \binom{2}{1} = \binom{s + t - 2}{t - 1}$.
*Case $t = 2$ (and $s \geq 2$).* A 2-colouring of $K_s$ either has a blue edge — giving a monochromatic $K_2$ in blue — or all edges are red, giving a monochromatic $K_s$ in red. Hence $R(s, 2) \leq s$. Conversely, a 2-colouring of $K_{s-1}$ in which every edge is red has no blue $K_2$ and no red $K_s$ (since $|V| < s$), so $R(s, 2) > s - 1$. Thus $R(s, 2) = s$, and $\binom{s + 2 - 2}{2 - 1} = \binom{s}{1} = s$ matches.
*Case $s = 2$ (and $t \geq 2$).* By symmetry $R(2, t) = t = \binom{t}{t - 1} = \binom{2 + t - 2}{t - 1}$.
So the bound holds at the boundary $\min(s, t) = 2$.
[/step]
[step:Apply the Ramsey recurrence $R(s, t) \leq R(s - 1, t) + R(s, t - 1)$ in the inductive step]
Now fix $s, t \geq 3$ and assume the bound $R(s', t') \leq \binom{s' + t' - 2}{t' - 1}$ holds whenever $s' + t' < s + t$ with $s', t' \geq 2$.
The $r = 2$ case of the [Existence of r-Set Ramsey Numbers](/theorems/2050) gives
\begin{align*}
R(s, t) = R^{(2)}(s, t) \leq R^{(1)}\!\left(R^{(2)}(s-1, t),\ R^{(2)}(s, t-1)\right) + 1.
\end{align*}
In the proof of that theorem we showed that $R^{(1)}(a, b) \leq a + b - 1$ by pigeonhole on $(r-1)$-subsets, i.e. on singletons, so
\begin{align*}
R(s, t) \leq R(s - 1, t) + R(s, t - 1) - 1 + 1 = R(s - 1, t) + R(s, t - 1).
\end{align*}
[guided]
Let us unwind why $R^{(1)}(a, b) \leq a + b - 1$. A 2-colouring of the 1-subsets of a set $V$ is just a 2-colouring of $V$ itself. By pigeonhole, if $|V| = a + b - 1$, then either at least $a$ elements receive colour red or at least $b$ elements receive colour blue. Hence $R^{(1)}(a, b) \leq a + b - 1$.
Substituting $a = R(s - 1, t)$ and $b = R(s, t - 1)$ into the general recurrence from the existence theorem,
\begin{align*}
R(s, t) &\leq R^{(1)}(R(s-1, t),\ R(s, t-1)) + 1 \\
&\leq [R(s-1, t) + R(s, t-1) - 1] + 1 \\
&= R(s-1, t) + R(s, t-1).
\end{align*}
This is the "edge" version of the recurrence — familiar from most textbook proofs of Ramsey's theorem, where one picks a vertex $v$ in $K_n$, sorts its $n - 1$ edges by colour, finds either $R(s-1, t)$ red neighbours or $R(s, t-1)$ blue neighbours, and combines with $v$ to build a monochromatic clique.
[/guided]
[/step]
[step:Apply the inductive hypothesis and Pascal's identity]
By the inductive hypothesis applied separately to $R(s - 1, t)$ and $R(s, t - 1)$ (both have strictly smaller $s' + t' = s + t - 1$):
\begin{align*}
R(s - 1, t) \leq \binom{(s - 1) + t - 2}{t - 1} = \binom{s + t - 3}{t - 1}, \qquad R(s, t - 1) \leq \binom{s + (t - 1) - 2}{(t - 1) - 1} = \binom{s + t - 3}{t - 2}.
\end{align*}
Combining with the previous step,
\begin{align*}
R(s, t) \leq \binom{s + t - 3}{t - 1} + \binom{s + t - 3}{t - 2}.
\end{align*}
By Pascal's identity, $\binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k}$ with $n = s + t - 2$ and $k = t - 1$:
\begin{align*}
\binom{s + t - 3}{t - 1} + \binom{s + t - 3}{t - 2} = \binom{s + t - 2}{t - 1}.
\end{align*}
Hence $R(s, t) \leq \binom{s + t - 2}{t - 1}$, completing the induction.
[/step]
[step:Derive the diagonal bound $R(s) \leq 4^s$ via the central binomial estimate]
Setting $t = s$ in the bound just proved,
\begin{align*}
R(s) = R(s, s) \leq \binom{2s - 2}{s - 1}.
\end{align*}
We invoke the standard bound $\binom{2m}{m} \leq 4^m$ for all $m \geq 0$. To verify it: by the binomial theorem,
\begin{align*}
4^m = 2^{2m} = (1 + 1)^{2m} = \sum_{k = 0}^{2m} \binom{2m}{k} \geq \binom{2m}{m},
\end{align*}
since $\binom{2m}{m}$ is one of the $2m + 1$ non-negative summands.
Applying this with $m = s - 1$,
\begin{align*}
R(s) \leq \binom{2s - 2}{s - 1} \leq 4^{s - 1} < 4^s,
\end{align*}
which gives the stated diagonal bound.
[/step]
