Problem 2157

Let the answer be $f(n,k)$. We will prove by induction on $n+k$ that
$$f(n,k) = \sum_{i=0}^{k-1} \binom{n}{i}.$$
Case $n=k=1$ is obvious.

Assume that $S$ is the maximum set of the desired sequences and let $T$ be the set of all binary sequences of length $n-1$. Define the sets $A, B, C$ as follows:
$$\begin{align*} A &= \{a \in T \mid \text{there exists } b \in S \text{ with } b = \overline{0a}, \text{ but there is no } c \in S \text{ with } c = \overline{1a}\} \\ B &= \{a \in T \mid \text{there exists } b \in S \text{ with } b = \overline{1a}, \text{ but there is no } c \in S \text{ with } c = \overline{0a}\} \\ C &= \{a \in T \mid \text{there exists } b, c \in S \text{ with } b = \overline{0a}, c = \overline{1a}\}. \end{align*}$$
Clearly, $f(n,k) = |A| + |B| + 2|C|$. Because we can't choose $k$ bits from the last $n-1$ bits of the sequences that produce all the binary sequences of length $k$, we have $|A| + |B| + |C| \le f(n-1,k)$. Now consider the set $C$. If $|C| \ge f(n-1,k-1)$, we can fix $k-1$ bits from the last $n-1$ bits to produce all sequences of length $k-1$. So because of the definition of $C$, by fixing these $k-1$ bits and the first bit, all sequences of length $k$ are produced, which is a contradiction. So we have
$$f(n,k) = |A| + |B| + 2|C| \le f(n-1,k) + f(n-1,k-1).$$
By induction and using Pascal's identity we get
$$\begin{align*} f(n,k) &\le \sum_{i=0}^{k-1} \binom{n-1}{i} + \sum_{i=0}^{k-2} \binom{n-1}{i} \\ &= 1 + \sum_{i=1}^{k-1} \binom{n-1}{i} + \sum_{i=0}^{k-2} \binom{n-1}{i} \\ &= 1 + \sum_{i=1}^{k-1} \left( \binom{n-1}{i} + \binom{n-1}{i-1} \right) \\ &= \binom{n}{0} + \sum_{i=1}^{k-1} \binom{n}{i} = \sum_{i=0}^{k-1} \binom{n}{i}. \end{align*}$$
For the equality example, simply choose all binary sequences with at most $k-1$ zeros. This way, by fixing any $k$ bits, the sequence with $k$ zeros will never be produced and we're done. ■