The question seems like it should be known, but I was not able to find it anywhere. 


How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ possible subsequences occur? 


For example, suppose $n=3$, and $k=2$. We want a set of binary strings of length $3$ so that if you look at the first and third symbols (or first two, or last two), you will see all $4$ patterns $00$, $01$, $10$, and $11$. For example, the strings with an even number of $1$s $\{ 000, 011, 110, 101\}$ induce all subsequences on each set of two positions. 


Let $f(n,k)$ be the minimum number. Trivially, $f(n,k) \ge 2^k$ so $f(3,2)=4$. 


I am interested in precise upper and lower bounds for $f(n,k)$. Bounds that are within a constant of each other (independent of $n$ and $k$) suffice for my purposes.



Repeats of all binary strings of length k
Orthogonal arrays were mentioned in another answer, but you are not requiring that each $k$-tuple occurs exactly once in every set of $k$ columns, but rather that each $k$-tuple occurs *at least once* in every set of $k$ columns.


What you are looking for is called a [covering array](http://math.nist.gov/coveringarrays/coveringarray.html). In the usual notation for covering and orthogonal arrays, $v$ is the size of the alphabet ($2$ in this case), $k$ corresponds to your $n$, and $t$ corresponds to your $k$. Some known upper bounds for the number of rows for small values of $t,k,v$ are listed in <http://www.public.asu.edu/~ccolbou/src/tabby/catable.html> - you are interested in the numbers for $(t,k,2)$.


