Can we prove $\sum_{i=1}^{k} \frac{\binom{n-2}{i}}{\binom{n}{i}} \le \frac{1}{(n-1)e}$ and arrive at an upper bound for $k$? Does this inequality hold true?
Given $\frac{n}{2} \ge k$,
$$\sum_{i=1}^{k} \frac{\binom{n-2}{i}}{\binom{n}{i}} \le \frac{1}{(n-1)e}$$
where $e = 2.71828\dots$
I have reduced this to 
$$\sum_{i=1}^{k} \frac{\binom{n-2}{i}}{\binom{n}{i}} = \sum_{i=1}^{k}\frac{(n-i)*(n-i-1)}{n*(n-1)}$$
$$ \le \sum_{i=1}^{n}\frac{(n-i)^{2}}{n*(n-1)} $$
$$ \le \frac{n}{n-1}\sum_{i=1}^{k}(1-\frac{i}{n})^2 $$
Using $1 + x \le e^x $, we get
$$ \le \frac{n}{n-1}\sum_{i=1}^{k}e^{\frac{-2*i}{n}} $$
Then I can apply sum of a GP and arrive at 
$$ LHS = \frac{n}{n-1} e^{\frac{-2}{n}}(\frac{1 - e^{\frac{2k}{n}}}{1 - e^{\frac{-2}{n}}}) $$
But now I am unable to relate this with the RHS and get stuck here.
Basically once this inequality is proven, I want to manipulate the terms and arrive at an upper bound for the value of k.
 A: Without restrictions on $n$ (and/or $k$), this will not be true. In particular, for $k=n-1$ you get
$$
\sum_{i=1}^{n-1} \frac{\binom{n-2}{i}}{\binom{n}{i}} = \frac{n-2}{3}.
$$
and for $k=\frac{n}{2}$ something that behaves asymptotically as
$$
\sum_{i=1}^{n-1} \frac{\binom{n-2}{i}}{\binom{n}{i}} = \frac{7}{6} n + o(n).
$$

You have
$$
\sum_{i=1}^{k} \frac{\binom{n-2}{i}}{\binom{n}{i}} = \sum_{i=1}^{k}\frac{(n-i)(n-i-1)}{n(n-1)} 
= \frac{1}{n(n-1)}\sum_{i=1}^{k}(n-i)(n-i-1)
$$
Now,
$$\begin{align}
\sum_{i=1}^{k}(n-i)(n-i-1) &= \sum_{i=1}^{k} \left(i^2 -i(2n-1) + (n-1)(n)\right) \\
&= \sum_{i=1}^{k} i^2 - (2n-1) \sum_{i=1}^{k}i + k(n-1)(n) \\
&= \frac{k(k+1)(2k+1)}{6} - (2n-1) \frac{k(k+1)}{2} + k(n-1)(n) \\
\end{align}$$
so 
$$\begin{align}
\sum_{i=1}^{k} \frac{\binom{n-2}{i}}{\binom{n}{i}} 
&= \frac{k(k+1)(2k+1)}{6n(n-1)} - \frac{2n-1}{n(n-1)}\frac{k(k+1)}{2} + k \\
&= \frac{1}{6n(n-1)}\left(k(k+1)(2k+1) - 3(2n-1)k(k+1) + 6n(n-1)k\right)
\end{align}$$
As mentioned above, for $k=n-1$ this simplifies to
$$
\sum_{i=1}^{k} \frac{\binom{n-2}{i}}{\binom{n}{i}} = \frac{n-2}{3}.
$$
and for $k=\frac{n}{2}$ we get
$$
\sum_{i=1}^{k} \frac{\binom{n-2}{i}}{\binom{n}{i}} = \frac{7n^2-18n+8}{6(n-1)} \operatorname*{\sim}_{n\to\infty} \frac{7n}{6} .
$$
