Let $f(n,k)$ be the answer and $\mathcal{F}$ a maximal family of strings that respect the condition. Let $$A=\{ a\in\{0,1\}^{n-1} | \text{there exists}~b\in\mathcal{F}~\text{with}~b=\overline{0a}~\text{, but there is no}~c\in\mathcal{F}~\text{with}~c=\overline{1a}\}$$$$B=\{ a\in\{0,1\}^{n-1} | \text{there exists}~b\in\mathcal{F}~\text{with}~b=\overline{1a}~\text{, but there is no}~c\in\mathcal{F}~\text{with}~c=\overline{0a}\} $$$$C=\{ a\in\{0,1\}^{n-1} | \text{there exist}~b,c\in\mathcal{F}~\text{with}~b=\overline{0a}~\text{and}~c=\overline{1a}\}. $$ Clearly we must have $|A\cup B\cup C|\le f(n-1,k)$(otherwise we can find $k$ bits from the last $n-1$ that span all the strings of length $k$) and $|C|\le f(n-1,k-1)$(other wise in $C$ we can find $k-1$ bits from the last $n-1$ that span all the strings of length $k-1$. But then taking into consideration the first bit, we will span all strings of length $k$), so $$f(n,k)=|\mathcal{F}|=|A|+|B|+2|C|\le f(n-1,k)+f(n-1,k-1).$$ Easy induction yields $f(n,k)\le\sum_{i=0}^{k-1}\binom{n}{i}.$ But inequality can be achieved: take all strings with at most $k-1$ bits equal to $1$. No matter how we chove $k$ bits, they will never all be equal to $1$.

This is the Sauer-Shelah lemma.

First left$ f(n,k)$ be that number we need first show $f(n,1)=1 , f(n,2)=n+1$ now use induction and try to prove for$ f(n,k)$ for this use induction on n first say $f(k,k)= 2^k -1 $ Now try to solve$ f(n,k)$ , now lets say the desired number for our induction to work for $f(n,k) $is$ S$ we show that if we have$ S+1 $binary string than we have all binary string being$ k $long for the sake of contradiction imagine we dont have the binary stirng$ ( a_1 ,a_2 ,... ,a_k)$ WLOG let$ a_1=1 $now group every$ S+1 $string into$ n $group the $ i_th $group has all the binary string which theire first number 1 apears in $a_i$ now we have $f(n,k)\le f(n-1,k-1)+f(n-2,k-1)+...+f(1,k-1)$ and if you just take a look at our induction than we should have $f(n,k)\le S$ and our induction is complete and $f(a,b)=0$ if $a<b$

Suppose that $f(n,k)$ is the proper value. By induction on $n$ , we'll show that for each $n \ge k$ we have : $$f(n,k)=\sum_{i=0}^{k-1}\binom{n}{i}$$Now let for a $n , k$ , $m$ binary sequences $A_{1} , A_{2} , ... , A_{m}$ are chosen. Consider $n-1$ first bits of each sequence and name these new sequences as $B_{1} , B_{2} , ... , B_{t(m)}$. So by our induction case for $n-1$ , we have : $$t(m) \le f(n-1 , k)$$Let $C_{1} , C_{2} , ... , C_{r(m)}$ be sequences from $B_{1} , B_{2} , ... , B_{t(m)}$ such that both $\overline C_{i}0$ and $\overline C_{i}1$ appears in $A_{i}$ sequences , then we'll show that $r(m) \le f(n-1 , k-1)$. Suppose not , thus there exist incidents $i_{1} , ... , i_{k-1} < n$ , which bits $r_{i_1} , r_{i_2} , ... , r_{i_{k-1}}$ create all possible sequences with $k-1$ bits among $C_{1} , C_{2} , ... , C_{r(m)}$. So attending to $C_{i}$'s definition , bits $r_{i_1} , r_{i_2} , ... , r_{i_{k-1}} , r_{n}$ produce all $k$-bit sequences in $A_i$'s , which is a contradiction. So by Pascal identity we have : $$m=r(m)+t(m) \le f(n-1 , k)+f(n-1 , k-1)=\sum_{i<k}\binom{n-1}{i}+\sum_{j<{k-1}}\binom{n-1}{j}=1+\sum_{i<{k-1}}\binom{n-1}{i}+\binom{n-1}{i+1}=\sum_{i<k}\binom{n}{i}$$Also for equality case , just consider an arbitrary sequence $A$ and each sequence which its distance from $A$ is less than $k$. So we're done.