Hi, my professor posted exactly one slide about Van der Waerden numbers and I simply don't have enough information to solve this. I tried looking online for help but none of the lower bounds seem to even closely resemble this one. Seeing as the professor gave us nothing to work with I assume we have to find some expression, e, and prove that 2^(k/2) >= e and then prove that W(k) >= e, but again, I am totally out of my element here. Could anyone please help me with this?
Edit: It's for two colours. So W(k, 2).
Color the interval $\{1,\ldots , N \} =[N]$ randomly uniformly in two colors. There are not more than $\binom{N}{2} < N^2/2$ arithmetic progressions of length $k$ in this interval. To see this, note that we can uniquely fix a $k$-AP by specifying its first two elements for instance. The probability that such a progression is monochromatic is $2 \cdot 2^{-k} = 2^{-k+1}$, as either all of the elements have color 1, or they all have color 2. So we expect less than $ N^2 2^{-k}$ monochromatic $k$-APs. If $N < 2^{k/2}$, then $$ N^2 2^{-k}<1. $$ So if $N<2^{k/2}$, we expect less than $1$ monochromatic $k$-APs. If every coloring of $[N]$ produces a monochromatic $k$-AP, then the expected value would be at least $1$. Therefore, there is a coloring of $[N]$ with no monochromatic $k$-AP.