After a bit of experimentation, I thought of the following conjecture:
Given any $n \in \mathbb{Z}_{\geq 0}$ and $k \in [0,2n]$, we have $$|\{S : (S \subseteq [0,n]) \land (k \not \in S+S)\}| = 2^{|n-k|} \cdot 3^{\lfloor ((n+1)-|n-k|)/2 \rfloor}.$$
I made a program that checks the conjecture for $n \in [0,9]$. I also made a Desmos plot of the right-hand side of the equation.
Is this conjecture true? If so, how can it be proved?
A few notes on notation:
- $[a,b]$ denotes the integer interval $\{a,...,b\}$.
- $A+A$ denotes the sumset $\{a_1+a_2 : a_1,a_2 \in A\}$.
Define $\sim$ on $[0,n]$ as $x\sim y$ iff $x=y$ or $x+y=k.$
$\sim$ is an equivalence relation which has equivalence classes of size $1$ and $2.$ Any $S$ without $k\in S+S$ can contain at most one element from each equivalence class.
For the equivalence classes with one element, that gives two option. For the equivalence classes with two elements, that gives three options.
So the count is $2^{n_1}3^{n_2},$ where $n_i$ is the number of equivalence classes of size $i.$
So you need to count the equivalence classes by size.
The number, $n_2,$ of equivalence classes of size $2$ is the number of solutions $a<b$ to $a+b=k.$
I’ll leave the rest to you.
This approach wouldn’t work for $k\notin S+S+S.$ The case of $S+S$ gives this nice approach where we partition $[0,n]$ into sets.