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.



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

  • 1
    $\begingroup$ What are your thoughts? What have you tried? $\endgroup$ – uniquesolution Jul 28 '18 at 18:20
  • $\begingroup$ It's unlikely that you can get the exact value. This will involve solving a $k$-th degree polynomial equation for an arbitrary $k$. There is no known method to algebraically solve large polynomial equations. What is wrong with your bound? Why isn't it good enough? $\endgroup$ – Batominovski Jul 28 '18 at 19:32
  • $\begingroup$ k is constant. I am very sorry for incomplete question. @Batominovski $\endgroup$ – sai Jul 28 '18 at 19:36
  • $\begingroup$ Doesn't matter. You are not giving us a very specific $k$ like: $k=2$, $k=3$, or $k=4$ (and for such $k$'s the problem is very trivial anyhow). If $k\geq 5$, then good luck. No known general way to solve a quintic. The only good approximation is probably $$n_\max \approx 2^{\frac{k-1}{2}}\,\frac{k}{\text{e}}\,.$$ $\endgroup$ – Batominovski Jul 28 '18 at 19:37
  • $\begingroup$ can you tell me how you got the approximate value? @Batominovski $\endgroup$ – sai Jul 28 '18 at 19:45

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.