It is well known [it's on Wolfram Mathworld, for example] that the probability of no runs of $k$ consecutive $1$'s will occur in a $\{0,1\}$-valued sequence of length $n$ is exactly equal to $$\frac{F^{(k)}_{n+2}}{2^n}\quad\quad(1)$$ where $F^{(k)}_l$ is the $l^{th}$ $k-$step Fibonacci number. For example if $k=6,$ the sequence $F_l^{(6)}$ starts with $1,1,2,4,8,16,32,63,\ldots$. The probability in (1) is of course the probability that no set of $1$'s supported on an arithmetic progression of length $k$ and difference $d=1$ exist. The numerator is the cardinality of all sequences which have no $k$ consecutive $1$'s.

What if I allowed an arbitrary $d$ (of course $kd\leq n$ must hold) and asked the question as follows:

*How many sequences of length $n$ support no all $1$-valued arithmetic progression of length $k$?*

How does the probability change? It goes down, of course. Is there any hope of a closed form solution? Is it tangentially related to Szemeredi's Theorem? There, the question is about the length that guarantees the existence of such a subsequence (when interpreted in characteristic function terms), given a density for a subset of $\{1,2,\ldots,n\}$ (relative number of 1's).

I am willing to assume a density that is not too far below $1/2$ for my question.