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.
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$.