How many sets give different answers? Consider a set $S$ of integers taken from $[n]$ and a given threshold $k$.  A query $x$ returns true if there exists an $s$ in $S$ such that $s-k \leq x \leq s+k$ and false otherwise.
Say that two sets are equivalent if they give the same answer to every possible query. How many different non-equivalent sets $S$ are there?
 A: We want to count the number $c_n$ of all $0/1$ strings such that all blocks of consecutive $1$s have length $\ge 2k+1$ (except possibly an initial or final string of length only $\ge \min\{k+1,n\}$). Let $a_n$ be the number of such strings ending $1$ (and hence in at least $k+1$ consecutive $1$s) and $b_n$ the number of such strings ending in $0$.
Then we have the recursions
$$\begin{align} a_n&=a_{n-1}+b_{n-k-1}\\
b_n&=b_{n-1}+a_{n-k-1}\end{align}$$
which are surprisingly symmetric. Hence for $c_n=a_n+b_n$ we have
$$\tag 1c_n=c_{n-1}+c_{n-k-1} $$
with initial values $$\tag2c_1=\ldots = c_{k+1}=2$$ (which suggests that we should define $c_0=0$). For $n\le$ small multiples of $k+1$ we can find polynomial expressions, but the general solution of $(1)$ uses the powers of the $k+1$ distinct roots $x_0,\ldots, x_k$ of 
$$ \tag 3x^{k+1}-x^{k}-1=0$$
and writes
$$ c_n=\sum_{i=0}^k \alpha_ix_i^n $$
with the $\alpha_i$ determined by the initial conditions $(2)$.
By a quick estimate using Bernoulli, the maximal root of $(3)$ is $<1+\frac1{\sqrt k}$, we get that $c_n=O((1+\frac1{\sqrt k})^n)$, but better estimates are possible. 
