TITLE: Maximum $n$ such that ${n \choose k} \,2^{1 - {k \choose 2}} < 1$ (where $k$ is a constant)
QUESTION [1 upvotes]: Maximum value of $n$ such that the expression given below does not exceed 1. ($k$ is a constant)
$${n \choose k} 2^{1 - {k \choose 2}}  < 1$$
Any hints on how to approach this problem.
Thanks.
Edit:
I tried doing the problem this way.
$${n \choose k} < \frac{n^k}{k!}$$
$${n \choose k} 2^{1 - {k \choose 2}} < \frac{n^k}{k!}2^{1 - {k \choose 2}}$$
$$\frac{n^k}{k!}2^{1 - {k \choose 2}} < 1 \Rightarrow n < \sqrt[k]{\frac{k!}{2^{1 - {k \choose 2}}}}$$
But, still $n_{max}$ can be greater than $\sqrt[k]{\frac{k!}{2^{1 - {k \choose 2}}}}$. How can i get the least upper bound for $n$.

REPLY [2 votes]: I shall prove that, for a positive integer $k$, the maximum natural number $n$, denoted by $n_k$, such that
$$\binom{n}{k}\leq 2^{\binom{k}{2}-1}$$
satisfies 
$$\lim_{k\to\infty}\,\frac{n_k}{k\,2^{\frac{k}{2}}}=\frac{1}{\text{e}\sqrt{2}}\,.\tag{*}$$
I also provide some bounds for the value of $n_k$.
First, we note that
$$\frac{\left(n_k-\frac{k-3}{2}\right)^k}{k!}>\binom{n_k+1}{k}>2^{\binom{k}{2}-1}\,,$$
where we have applied the AM-GM Inequality
$$\begin{align}(n_k+2-k)&(n_k+3-k)\cdots (n_k)(n_k+1)\\
&\leq \left(\frac{(n_k+2-k)+(n_k+3-k)+\ldots +(n_k)+(n_k+1)}{k}\right)^k
\\&=\left(n_k-\frac{k-3}{2}\right)^k\,.\end{align}$$
That is,
$$n_k-\frac{k-3}{2}>\sqrt[k]{2^{\binom{k}{2}-1}\,k!}=2^{\frac{k-1}{2}}\,\sqrt[k]{\frac{k!}{2}}\geq 2^{\frac{k-1}{2}}\left(\frac{\pi k}{2}\right)^{\frac{1}{2k}}\,\left(\frac{k}{\text{e}}\right)>2^{\frac{k-1}{2}}\,\left(\frac{k}{\text{e}}\right)\,,$$
where we have used the Stirling Approximation $$k!\geq \sqrt{2\pi k}\left(\frac{k}{\text{e}}\right)^k\,.$$
This shows that $$n_k>2^{\frac{k-1}{2}}\,\left(\frac{k}{\text{e}}\right)+\frac{k-3}{2}\,.$$
Now, 
$$\frac{(n_k+1-k)^k}{k!}<\binom{n_k}{k}\leq 2^{\binom{k}{2}-1}\,.$$
This gives
$$n_k-(k-1)<\sqrt[k]{2^{\binom{k}{2}-1}\,k!}\leq 2^{\frac{k-1}{2}}\,\left(\frac{\text{e}^2k}{4}\right)^{\frac{1}{2k}}\,\left(\frac{k}{\text{e}}\right)\,,$$
in which we have used the Stirling approximation
$$k!\leq \sqrt{\text{e}^2k}\,\left(\frac{k}{\text{e}}\right)^k\,.$$
That is,
$$n_k<2^{\frac{k-1}{2}}\,\left(\frac{k}{\text{e}}\right)\,\Biggl(1+O\left(\frac{\ln(k)}{k}\right)\Biggr)+k-1\,,$$
noting that
$$\left(\frac{\text{e}^2k}{4}\right)^{\frac{1}{2k}}=1+\frac{\ln(k)}{2k}+\frac{1-\ln(2)}{k}+O\left(\left(\frac{\ln(k)}{k}\right)^2\right)=1+O\left(\frac{\ln(k)}{k}\right)\,.$$
In conclusion, we have
$$2^{\frac{k-1}{2}}\,\left(\frac{k}{\text{e}}\right)+\frac{k-3}{2}<n_k<2^{\frac{k-1}{2}}\,\left(\frac{k}{\text{e}}\right)\,\Biggl(1+O\left(\frac{\ln(k)}{k}\right)\Biggr)+k-1\,.$$
This proves (*).  In fact, we can also show that, for all $k\geq 22$, 
$$2^{\frac{k-1}{2}}\,\left(\frac{k+\frac{1}{2}\,\ln(k)+\frac{1}{5}}{\text{e}}\right)<n_k<2^{\frac{k-1}{2}}\,\left(\frac{k+\frac{1}{2}\,\ln(k)+\frac{1}{3}}{\text{e}}\right)\,,$$
using
$$\left(\frac{\pi k}{2}\right)^{\frac{1}{2k}}=1+\frac{\ln(k)}{2k}+\frac{\ln(\pi)-\ln(2)}{2k}+O\left(\left(\frac{\ln(k)}{k}\right)^2\right)$$
and
$$\frac{1}{5}<\frac{\ln(\pi)-\ln(2)}{2}<1-\ln(2)<\frac{1}{3}\,.$$
Anyhow, the best approximator of $n_k$ is still $m_k:=2^{\frac{k-1}{2}}\,\sqrt[k]{\dfrac{k!}{2}}$, albeit being trickier to calculate, since we have
$$m_k+\frac{k-3}{2}< n_k < m_k+k-1\,.$$
{"set_name": "stack_exchange", "score": 1, "question_id": 2865466}