Abstract
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≤k then w(r,k)>p⋅wr−rp,k−1. This recurrence gives the lower bound w(r,p+1)>pr−12p when r≤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.