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