Ramsey numbers Olympiad combo

Question

Show that if l,s are positive integers, then $r(l,s) \leq {l + s - 2 \choose l - 1} $

Answer 1

In order to prove this claim, I will use the result $r(l, s) \leq r(l - 1, s) + r(l, s - 1)$. A proof of this inequality is shown here.

When $l = s = 2$, we have $r(2, 2) = 2$, and the claim holds. Now if the relation holds for $r(l - 1, s)$ and $r(l, s - 1)$, then one has

$$r(l, s) \leq r(l - 1, s) + r(l, s - 1) = {l + s - 2\choose l -1}, $$

where the last equality follows from using the induction hypothesis with Pascal's Identity. By induction, the conclusion follows.