  In this paper we prove a new recurrence relation on the van der Waerden
numbers, $w(r,k)$. In particular, if $p$ is a prime and $p\leq k$ then $w(r, k)
> p \cdot \left(w\left(r - \left\lceil \frac{r}{p}\right\rceil, k\right)
-1\right)$. This recurrence gives the lower bound $w(r, p+1) > p^{r-1}2^p$ when
$r \leq p$, which generalizes Berlekamp's theorem on 2-colorings, and gives the
best known bound for a large interval of $r$. The recurrence can also be used
to construct explicit valid colorings, and it improves known lower bounds on
small van der Waerden numbers.
