Erdős's exponential lower bound for Ramsey numbers

Set $n = \lfloor 2^{k/2} \rfloor$. From the first-moment computation above, $\mathbb{E}[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}$. If we show $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$, then since $X$ only takes nonnegative integer values, some 2-coloring must achieve $X=0$ — otherwise $X \ge 1$ always, forcing $\mathbb{E}[X]\ge 1$. A coloring with $X=0$ has no monochromatic $k$-clique at all.

Bound the binomial coefficient by $\binom{n}{k} \le n^k/k!$, and since $n \le 2^{k/2}$ we get $n^k \le 2^{k^2/2}$. Substituting into the expectation formula, $\mathbb{E}[X] \le \dfrac{2^{k^2/2}\cdot 2^{1-\binom{k}{2}}}{k!}$.

Simplify the exponent: $\dfrac{k^2}{2} + 1 - \dfrac{k(k-1)}{2} = 1 + \dfrac{k^2 - k^2 + k}{2} = 1 + \dfrac{k}{2}$. So $\mathbb{E}[X] \le \dfrac{2^{1+k/2}}{k!}$, and it suffices to show $k! > 2^{1+k/2}$ for every $k \ge 3$.

Check this by induction on $k$. Base case $k=3$: $3! = 6$ and $2^{1+3/2} = 2^{2.5} \approx 5.657$, and indeed $6 > 5.657$. For the inductive step, suppose $k! > 2^{1+k/2}$ holds at some $k \ge 3$. Then $(k+1)! = (k+1)\cdot k! > (k+1)\cdot 2^{1+k/2}$, and since $k+1 \ge 4 > \sqrt2$, this exceeds $\sqrt2 \cdot 2^{1+k/2} = 2^{1+(k+1)/2}$, which is exactly the claim at $k+1$. So $k! > 2^{1+k/2}$ holds for every $k \ge 3$, which gives $\binom{n}{k}\,2^{1-\binom{k}{2}} < 1$ as needed.

Therefore a 2-coloring of $K_n$ with no monochromatic $k$-clique exists, so $R(k,k) > n = \lfloor 2^{k/2}\rfloor$. Since $\lfloor x\rfloor + 1 > x$ for every real $x$, this gives $R(k,k) \ge \lfloor 2^{k/2}\rfloor + 1 > 2^{k/2}$, which is exactly $R(k,k) > 2^{k/2}$.