Upper bound for $\frac{\sum_{i=0}^{k} \binom{n-2}{i}}{\sum_{i=0}^{k} \binom{n}{i}}$ How to simplify $P = \frac{\sum_{i=0}^{k} \binom{n-2}{i}}{\sum_{i=0}^{k} \binom{n}{i}}$ to get an upper bound in terms of $n$ and $k$. Here $k \le n$ and $\binom{n}{r}$ is the binomial coefficient that denotes the number of ways to choose $r$ objects from a set of $n$ objects.

$P$ is the probability that 2 fixed objects $u,v \in S$ where $S$ is a set of $n$ distinct objects, are both not present in a random subset $C$ of $S$ where $|C| \le k$ so trivially $P \le 1$

Interpretation:

Numerator = Number of subsets of size $\le k$ without $u,v$

Denominator = All possible subsets with size $\le k$
Let $F_n$ and $f_n$ be respectively CDF and pmf of $B(n,\frac 1 2)$. Then $$P=\frac 1 4\frac {F_{n-2}(k)}{F_n(k)}=\frac 1 4\frac {F_{n-2}(k)}{F_{n-2}(k)-\frac 3 4f_{n-2}(k)-\frac 1 4f_{n-2}(k-1)}$$ From CLT we get that for $k\ge \frac n 2-O(n^{\frac 1 2})$ $$P= \frac 1 4+O(n^{-\frac 1 2})\tag 1$$
For $k=o(n)$, we easily get $P\to 1$
and if $k= an$ for $0&lt;a&lt;\frac 1 2$, let $r=\frac{a}{1-a}$ to get $$P\to \frac 1 {(1+r)^2}=(1-a)^2\tag 2$$

which agrees with the other two regimes. This result is very easy to explain - when $k=an&lt;\frac n 2$, most of the sets in consideration are very close in size to $k$ and chances that two elements don't belong to a specific such set are $(1-a)^2$.
Let $F_n$ and $f_n$ be respectively CDF and pmf of $B(n,\frac 1 2)$. Then $$P=\frac 1 4\frac {F_{n-2}(k)}{F_n(k)}=\frac 1 4\frac {F_{n-2}(k)}{F_{n-2}(k)-\frac 3 4f_{n-2}(k)-\frac 1 4f_{n-2}(k-1)}$$ From CLT we get that for $k\ge \frac n 2-O(n^{\frac 1 2})$ $$P= \frac 1 4+O(n^{-\frac 1 2})\tag 1$$
For $k=o(n)$, we easily get $P\to 1$
and if $k= an$ for $0&lt;a&lt;\frac 1 2$, let $r=\frac{a}{1-a}$ to get $$P\to \frac 1 {(1+r)^2}=(1-a)^2\tag 2$$

which agrees with the other two regimes. This result is very easy to explain - when $k=an&lt;\frac n 2$, most of the sets in consideration are very close in size to $k$ and chances that two elements don't belong to a specific such set are $(1-a)^2$.