, 2022

Let $B$ be the set of all sequences of 0 and 1 of length $n-1$, thus $|B| = 2^{n-1}$. It is clear that the set $A$ obtained by adding 01 at the end of any sequence from $B$ is good. Therefore $a_n \le 2^{n-1}$.

A sequence of length $n$ with all zeroes can be obtained either by the sequence with all zeroes of length $n+1$ or by a sequence of length $n+1$ with only one entry 1. In both cases the number of sequences obtained by deleting one entry is at most 3. By analogy, from a sequence of length $n+1$ with all ones or with exactly one zero one obtains at most 3 sequences of length $n$. Only from the sequences of length $n+1$ with alternating 0 and 1 (or 1 and 0) one obtains $n+1$ sequences of length $n$. Note that if both alternating sequences are in $A$ then the two sequences of length $n$ with alternating 0 and 1 or 1 and 0 are obtained by two ways. Therefore
$$2^n \le 6 + (n+1) + (a_n - 3)n \iff \frac{2^n + 2n - 7}{n} \le a_n.$$