Probability with Martingales
This was answered here using bounds and here using PGF. I would like to try inclusion-exclusion.
Let $H_1, H_2, ...$ be independent events with $P(H_k) = p$ where $H_k$ means the kth toss is heads.
It seems that ($\cap$ omitted)
$$A_0 = H_1$$
$$A_1 = H_2 \cup H_3$$
$$A_2 = (H_4H_5) \cup (H_5H_6) \cup (H_6H_7) := \bigcup_{i=1}^{3} E_{2,i}$$
$$A_3 = (H_8H_9H_{10}) \cup ... \cup (H_{13}H_{14}H_{15}) := \bigcup_{i=1}^{6} E_{3,i}$$
$$\vdots$$
$$A_k = (H_{2^k}...H_{2^k + k-1}) \cup ... \cup (H_{2^{k+1} - k}...H_{2^{k+1} - 1}) := \bigcup_{i=1}^{2^k - k + 1} E_{k,i}$$
So by inclusion-exclusion, we have
$$P(A_0) = p$$
$$P(A_1) = p + p - p^2$$
$$P(A_2) = 3p^2 - 2p^3$$
$$P(A_3) = \ldots$$
It gets tricky starting $A_3$
$$P(A_3) = P\left(\bigcup_{i=1}^{6} E_{3,i}\right)$$
Attacking that directly is going to lead to problems.
What about this?
$$P\left(\bigcup_{i=1}^{6} E_{3,i}\right)$$
$$ = P\left(\bigcup_{i=1,4} E_{3,i} \cup \bigcup_{i=2,5} E_{3,i} \cup \bigcup_{i=3,6} E_{3,i} \right)$$
$$ := P(F_{3,1} \cup F_{3,2} \cup F_{3,3})$$
Each $F$ is a union of disjoint sets.
- Also, I notice independence isn't being used. I guess the $H_k$'s and the $A_k$'s are independent. What about some subset of the the $E$'s? The $F$'s?
The events you are uniting are not independent, and they intersect in intricate ways, so using inclusion-exclusion on them will quickly lead to a mess. Take for instance the union $$H_8H_9H_{10} \cup H_9H_{10}H_{11}\cup\cdots\cup H_{13}H_{14}H_{15}, $$ also known as $A_3$. Taking the sets $H_iH_{i+1}H_{i+2}$ in the union one at a time, they each have probability $p^3$, but intersecting them two at a time will yield events like $H_8H_9H_{10}\cap H_9H_{10}H_{11}=H_8H_9H_{10}H_{11}$ which have probability $p^4$ but also events like $H_8H_9H_{10}\cap H_{10}H_{11}H_{12}=H_8H_9H_{10}H_{11}H_{12}$ with probability $p^5$ and also events like $H_8H_9H_{10}\cap H_{13}H_{14}H_{15}$ with probability $p^6$. You will need to count how many there are of each type. Intersecting them three at a time will yield events with probabilities ranging from $p^5$ to $p^8$, and you're not even done with intersections four at a time and five at a time. It is not obvious whether the general form for $P(A_k)$ is compactly expressible in terms of $p$.
Better to use the bounding approach in the first answer you cited. The $p\ge\frac12$ case of the bounding argument uses the events $E_i$ defined in the hint; the $E_i$ have the advantage of being independent events, so an inclusion-exclusion argument (or finding the probability of a complement event) leads to a tidy expression. It is true that the bounding approach is not calculating the exact prob of $A_k$; rather, it is calculating upper and lower bounds on $P(A_k)$, which are sharp enough to apply the Borel-Cantelli lemma.