Let build a set $A$ by this rule: for $i$ from $0$ to $n - 1$ with probability of $\frac{1}{2}$ we add this number to set $A$.
Then we generate set $B = A + A := \{a_1 + a_2: a_1 \in A, a_2 \in A\}$
And the question is to find upper bound on probability $P(k \notin B)$ as precise as possible.
I have not idea for this question.
Thanks
$k\in B$ iff there exists any $a$ such that $a\in A \;\wedge\; (k-a)\in A$.
Further such an $a$ must also satisfy: $\max\{0,k-n+1\}\leq a \leq \min\{k, n-1\}$ though due to symmetry we need only consider the upper values ($k-a$ takes care of the lower half).
There is one special case to beware: when $k$ is even, $\tfrac k 2\in A$ if and only if $(k-\tfrac k 2)\in A$.
$$\mathsf P(k\in B) = 1 - \mathsf P\left(\bigcap_{a=\lceil k/2\rceil}^{\min\{k,n-1\}} \Big(\{a\notin A\}\;\cup\;\{(k-a)\notin A\}\Big)\right) \\ = 1 -\prod_{a=\lceil k/2\rceil}^{\min\{k,n-1\}} \mathsf P\Big(\{a\notin A\}\;\cup\;\{(k-a)\notin A\}\Big) $$
Can you complete?
