Let $S \subset \mathbb{N}$ with each number $n \in S$ with probability $1/2$. Let further $k,l \in \mathbb{N}$ with $k \ge 2$ and let $A_l$ be the probability that $S$ contains an arithmetic progression of the form $$k-b, k, k+b, \ldots, k+(\lceil \log_2(kl2^{k-1})\rceil-2)b.$$
Show that $\mathbb{P}[A_l] \le 1/l$ and deduce from this that $S$ does not contain an arithmetic progression of infinite length.
I think the way to go here is to assume that $S$ is sorted increasingly, i.e.:
$$s_1 < s_2 < s_3 \ldots .$$
I recognise that the chance of $S$ containing a specific arithmetic progression is given by
$$\frac{1}{2^{\log_2(kl2^{k-1})}} = \frac{1}{kl2^{k-1}},$$
but I do not see how to estimate the probability of $S$ containing no arithmetic progression with this. Could you please give me a hint?
The finite arithmetic progressions are fully determined by $l, k, b$. For a given choice of those parameters, denote the corresponding arithmetic progression by $T(l,k,b)$.
Fix $l$. As you say, the probability of $S$ containing a specific arithmetic progression $T(l,k,b)$ in the given form is $\frac{1}{k l 2^{k-1}}$. We next ask: if we also fix $k$, then what's the probability that $T(l,k,b) \subseteq S$ for some $b$? Well, $S$ needs to include $k-b$, so there are only $k$ possible choices of $b$, so $$P[\exists b \text{ such that } T(l,k,b) \subseteq S] \le \sum_{b=1}^k P[T(l,k,b) \subseteq S] = \sum_{b=1}^k \frac{1}{k l 2^{k-1}} = \frac{1}{l 2^{k-1}}.$$
Thus for our fixed $l$ we have $$\begin{align} P[A_l] &= P[\exists k,b \text{ such that } T(l,k,b) \subseteq S] \\ &\le \sum_{k=2}^\infty P[\exists b \text{ such that } T(l,k,b) \subseteq S] \\ &\le \sum_{k=2}^\infty \frac{1}{l 2^{k-1}} \\ &= \frac{1}{l} \end{align}$$ which proves the hinted intermediate claim.
Your question focused on the first part of the proof, so I'm not sure if you want spoilers on finishing once you've proven the hint proposition. Therefore I'll use hidden text: