[proofplan] This is the celebrated Erdős probabilistic argument: to show $R(s) > n$ for every $n \leq 2^{s/2}$, we exhibit a 2-colouring of $K_n$ with no monochromatic $K_s$. Colour each edge independently red or blue with probability $\tfrac{1}{2}$. For any fixed $s$-subset $K$, the event "$K$ is monochromatic" has probability $2 \cdot 2^{-\binom{s}{2}}$. A union bound over the $\binom{n}{s}$ possible $s$-subsets, combined with the factorial lower bound $s! \geq 2^{s/2 + 1}$ for $s \geq 3$, gives probability strictly less than $1$. Hence the complementary event — *no* monochromatic $K_s$ — has strictly positive probability, so some concrete colouring witnesses $R(s) > n$. [/proofplan] [step:Fix the random colouring and identify the bad events] Fix $s \geq 3$ and let $n$ be any integer with $1 \leq n \leq 2^{s/2}$. Let $V := \{1, 2, \ldots, n\}$ be the vertex set of $K_n$. Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space carrying an i.i.d. family $(X_e)_{e \in V^{(2)}}$ of $\{\text{red}, \text{blue}\}$-valued Bernoulli random variables with $\mathbb{P}(X_e = \text{red}) = \mathbb{P}(X_e = \text{blue}) = \tfrac{1}{2}$. This defines a random 2-colouring \begin{align*} X : \Omega \times V^{(2)} &\to \{\text{red}, \text{blue}\} \\ (\omega, e) &\mapsto X_e(\omega). \end{align*} For each $s$-subset $K \in V^{(s)}$, let \begin{align*} A_K := \{\omega \in \Omega : X_e(\omega) \text{ is the same colour for every } e \in K^{(2)}\} \end{align*} be the event that $K$ is monochromatic. Our goal is to show $\mathbb{P}\!\left(\bigcup_{K \in V^{(s)}} A_K\right) < 1$, so that the complementary event — no monochromatic $K_s$ — has strictly positive probability. [/step] [step:Compute the probability that a fixed $s$-subset is monochromatic] Fix $K \in V^{(s)}$. The set $K^{(2)}$ has exactly $\binom{s}{2}$ elements, and the random variables $(X_e)_{e \in K^{(2)}}$ are i.i.d.\ uniform on $\{\text{red}, \text{blue}\}$. The event $A_K$ decomposes as $A_K = A_K^{\text{red}} \sqcup A_K^{\text{blue}}$, where $A_K^{\text{red}} := \{X_e = \text{red} \text{ for all } e \in K^{(2)}\}$ and analogously for blue. By independence, \begin{align*} \mathbb{P}(A_K^{\text{red}}) = \prod_{e \in K^{(2)}} \mathbb{P}(X_e = \text{red}) = \left(\tfrac{1}{2}\right)^{\binom{s}{2}} = 2^{-\binom{s}{2}}, \end{align*} and the same holds for blue. The two sub-events are disjoint (a colouring with $\binom{s}{2} \geq 1$ edges cannot be both all-red and all-blue), so \begin{align*} \mathbb{P}(A_K) = 2 \cdot 2^{-\binom{s}{2}}. \end{align*} [/step] [step:Apply the union bound over all $s$-subsets] There are $\binom{n}{s}$ many $s$-subsets of $V$. By the union bound (i.e., countable subadditivity of probability measures applied to the finite union), \begin{align*} \mathbb{P}\!\left(\bigcup_{K \in V^{(s)}} A_K\right) \leq \sum_{K \in V^{(s)}} \mathbb{P}(A_K) = \binom{n}{s} \cdot 2 \cdot 2^{-\binom{s}{2}}. \end{align*} Using the standard bound $\binom{n}{s} \leq \frac{n^s}{s!}$ (immediate from $\binom{n}{s} = \frac{n(n-1)\cdots(n-s+1)}{s!} \leq \frac{n^s}{s!}$), \begin{align*} \mathbb{P}\!\left(\bigcup_{K} A_K\right) \leq \frac{n^s}{s!} \cdot 2 \cdot 2^{-s(s-1)/2}. \end{align*} [guided] The union bound is the key probabilistic input. For any collection of events $\{A_K\}$, \begin{align*} \mathbb{P}\!\left(\bigcup_K A_K\right) \leq \sum_K \mathbb{P}(A_K). \end{align*} This holds without any independence assumption — it is just subadditivity of the measure $\mathbb{P}$. Why is the union bound tight enough here? Because the events $A_K$ are quite "spread out": most pairs of $s$-subsets $K, K'$ share few edges, so their monochromaticity events have low correlation. In fact one can do much better with the Lovász Local Lemma, but the basic union bound already delivers the exponential lower bound $2^{s/2}$. Upper-bounding the binomial coefficient is standard: \begin{align*} \binom{n}{s} = \frac{n(n-1)(n-2)\cdots(n-s+1)}{s!} \leq \frac{n^s}{s!}, \end{align*} since each factor in the numerator is at most $n$. [/guided] [/step] [step:Bound $n^s$ using $n \leq 2^{s/2}$] Since $n \leq 2^{s/2}$, we have $n^s \leq 2^{s \cdot s/2} = 2^{s^2/2}$. Substituting, \begin{align*} \mathbb{P}\!\left(\bigcup_{K} A_K\right) \leq \frac{2^{s^2/2}}{s!} \cdot 2 \cdot 2^{-s(s-1)/2} = \frac{2}{s!} \cdot 2^{s^2/2 - s(s-1)/2}. \end{align*} The exponent simplifies: $s^2/2 - s(s-1)/2 = (s^2 - s^2 + s)/2 = s/2$. Hence \begin{align*} \mathbb{P}\!\left(\bigcup_{K} A_K\right) \leq \frac{2 \cdot 2^{s/2}}{s!} = \frac{2^{s/2 + 1}}{s!}. \end{align*} [/step] [step:Verify the factorial inequality $s! \geq 2^{s/2 + 1}$ for $s \geq 3$] We claim that $s! \geq 2^{s/2 + 1}$ for every integer $s \geq 3$, with strict inequality for $s \geq 4$. *Base case $s = 3$.* $3! = 6$ and $2^{3/2 + 1} = 2^{5/2} = 4\sqrt{2} \approx 5.657$. Since $6 > 4\sqrt{2}$, the inequality holds strictly. *Inductive step.* Assume $s! \geq 2^{s/2 + 1}$ for some $s \geq 3$. Then \begin{align*} (s+1)! = (s + 1) \cdot s! \geq (s + 1) \cdot 2^{s/2 + 1}. \end{align*} We want $(s+1)! \geq 2^{(s+1)/2 + 1} = 2^{s/2 + 1} \cdot 2^{1/2} = \sqrt{2} \cdot 2^{s/2 + 1}$. It therefore suffices that $s + 1 \geq \sqrt{2}$, which holds for every $s \geq 1$ (since $s + 1 \geq 2 > \sqrt{2}$). By induction, $s! \geq 2^{s/2 + 1}$ for every $s \geq 3$. [/step] [step:Combine the estimates and conclude] Combining the previous two steps, \begin{align*} \mathbb{P}\!\left(\bigcup_{K \in V^{(s)}} A_K\right) \leq \frac{2^{s/2 + 1}}{s!} \leq \frac{2^{s/2 + 1}}{2^{s/2 + 1}} = 1. \end{align*} For $s = 3$, the factorial inequality is strict ($6 > 4\sqrt{2}$), so the bound above is strict: $\mathbb{P}(\bigcup A_K) < 1$. For $s \geq 4$, in the inductive step the factor $s + 1 \geq 5 > \sqrt{2}$ gives strict inequality, so iterating from $s = 3$ preserves strictness. In every case $s \geq 3$, \begin{align*} \mathbb{P}\!\left(\bigcup_{K \in V^{(s)}} A_K\right) < 1. \end{align*} Taking complements, \begin{align*} \mathbb{P}\!\left(\bigcap_{K \in V^{(s)}} A_K^c\right) = 1 - \mathbb{P}\!\left(\bigcup_{K \in V^{(s)}} A_K\right) > 0. \end{align*} Since this event has strictly positive probability, there exists at least one $\omega^\star \in \Omega$ for which no $s$-subset of $V$ is monochromatic. The deterministic 2-colouring $e \mapsto X_e(\omega^\star)$ of the edges of $K_n$ has no monochromatic $K_s$, so $R(s) > n$. This conclusion holds for every integer $n$ with $1 \leq n \leq 2^{s/2}$. In particular, taking $n = \lfloor 2^{s/2} \rfloor$, we get $R(s) > \lfloor 2^{s/2} \rfloor$, and since $R(s)$ is an integer, $R(s) \geq \lfloor 2^{s/2} \rfloor + 1 \geq 2^{s/2}$, completing the proof. [/step]