Estimate $\left(\begin{array}{c}n\\ k\end{array}\right)\left(1-2^{-k}\right)^{n-k}<1$. For a fixed $k$, I want to find $n$ such that the inequality $\left(\begin{array}{c}n\\ k\end{array}\right)\left(1-2^{-k}\right)^{n-k}<1$ holds. The bound I want to seek is $n>(1+o(1))\ln{2}\cdot k^{2}\cdot2^{k}$.
My attempt is using the inequality
$$
\left(\begin{array}{c}n\\ k\end{array}\right)<\left(\dfrac{en}{k}\right)^{k} {\rm{\ and\ }} \left(1-2^{-k}\right)^{n-k}<\exp\left({\dfrac{-(n-k)}{2^{k}}}\right)
$$
and trun to estimate $n$ by the inequality
$$
\left(\dfrac{en}{k}\right)^{k}\exp\left({\dfrac{-(n-k)}{2^{k}}}\right)<1.
$$
But I cannot go further.
Thanks in advanced.
 A: You have the right ideas. Let's bound $(1 - 2^{-k})^{-k}$ by $2$ to avoid dealing with it, set $n = \alpha \cdot \ln 2 \cdot k^2 \cdot 2^k$, and apply the bounds you suggest. Then we have
\begin{align}
   \binom nk (1 - 2^{-k})^{n-k} &\le 2\left(\frac{ne}{k}\right)^k e^{-n/2^k} \\
 &= 2 \left(\alpha \cdot e\ln 2 \cdot k \cdot 2^k\right)^k \cdot e^{-\alpha \cdot \ln 2 \cdot k^2} \\
 &= 2 \left(\alpha \cdot e\ln 2 \cdot k \cdot 2^k\right)^k \cdot 2^{-\alpha  \cdot k^2} \\
 &= 2 \left(\alpha \cdot e \ln 2 \cdot k \cdot 2^{(1-\alpha)k} \right)^k.
\end{align}
So we see that if $\alpha$ is any constant larger than $1$, we have a decaying exponential inside the power of $k$, which makes this expression go to $0$ for $k$ large enough. More precisely, it's enough to take $\alpha = 1 + \frac{2\log_2 k}{k}$ to turn the $2^{(1-\alpha)k}$ into $\frac1{k^2}$ and also make this expression approach $0$ as $k \to \infty$.
In particular, if an expression approaches $0$ as $k \to \infty$, it will eventually be less than $1$, provided $k$ is large enough.
Having something that works for large enough $k$ is fine, because our asymptotic expression for $n$ only needs to be true for large enough $k$. Actually, setting $\alpha = 1 + \frac{2\log_2 k}{k}$ only works for $k \ge 5$, but we can just avoid that by setting
$$
   \alpha = \begin{cases}
       1000 & k < 5 \\
       1 + \frac{2\log_2 k}{k} & k \ge 5
   \end{cases}
$$
which works for all $k$ and is still $1+o(1))$ as $k \to \infty$.
