Sets without k-term progressions can have many shorter progressions

Let f_(s,k)(n) be the maximum possible number of s-term arithmetic progressions in a sequence a₁ s ≥ 3, we prove that Lim_(n→∞) log f_(s,k)(n)/log n = 2, which answers an old question of Erdős. In fact, we prove upper and lower bounds for f_(s,k)(n) which show that its growth is closely related to the bounds in Szemeredi's theorem.