Consider a sequence of $n\geq 1000$ coin flips. Prove that the probability that there isn't a subsequence of $\lfloor \log n - 2\log\log n - 1 \rfloor$ consecutive heads is at most $\frac{1}{n}$.
I am aware that there are general recursions for probabilities of this kind but I am trying to find a slick way to do the above, with or without such recursions, as in the pedestrian way I get stuck into calculations.
Any help appreciated!
Elaborating on my comment:
The probability that a fixed run of length $\lfloor\log n-2\log\log n-1\rfloor$ is all heads is \begin{equation} 2^{-(\lfloor \log n-2\log\log n-1\rfloor)}\geq \frac{\log^2 n}{n}. \end{equation}
Splitting the run of $n$ trials into at least $n/\log n$ disjoint blocks of that length (which can be done as each block has length $<\log n$), clearly the probability none of these blocks are all heads is an upper bound for your event. This probability by independence is at most \begin{equation} \bigg(1-\frac{\log^2 n}{n}\bigg)^{n/\log n}\leq 2^{-\log n}=\frac{1}{n}. \end{equation} The inequality is $1-x\leq 2^{-x}$, valid for $x\geq 0$.