0
$\begingroup$

I have a small doubt and will much appreciate it if someone will clear it up. For large $k$ and $n=\lfloor 2^{k/2}\rfloor $, why are the following inequalities true:

  1. $\displaystyle\left(\frac{n}{2^{k/2}}\right)^k\le 1$.

  2. $\displaystyle\frac{2^{1+k/2}}{k!}$ is much smaller then 1.

Thanks a lot.

$\endgroup$
  • 2
    $\begingroup$ Do you mean $n=2^{\lfloor k/2\rfloor}$? $\endgroup$ – Brian M. Scott May 26 '12 at 4:42
  • $\begingroup$ @BrianM.Scott I think you are right. If not inequality 1 is trivial. $\endgroup$ – Eugene May 26 '12 at 4:43
  • 1
    $\begingroup$ much smaller .... what exactly does that really mean? $\endgroup$ – Squirtle May 26 '12 at 4:49
1
$\begingroup$

Assuming that you made no typos, we have that $\lfloor 2^{k/2} \rfloor \leq 2^{k/2}$. So clearly

$$ \dfrac{n}{2^{k/2}} \leq 1 $$

and inequality (1) follows.

For inequality (2) just think about it in the following way:

$$ \dfrac{2^k}{k!} = \dfrac{2\cdots 2}{1\cdots k} = \dfrac{2}{1} \cdot \dfrac{2}{2} \cdots \dfrac{2}{k} $$ so when $k$ is large clearly the denominator is greater than the numerator. Since $1 + k/2 < k$ for $k$ sufficiently large, inequality $2$ follows.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

For (2), suppose first that $k=2m$ is even. Then $$\frac{k!}{2^m}=\frac{\big(1\cdot3\cdot5\cdot\ldots\cdot(2m-1)\big)(2\cdot4\cdot6\cdot\ldots\cdot 2m)}{2^m}=\big(1\cdot3\cdot5\cdot\ldots\cdot(2m-1)\big)m!\;,$$ so $$\frac{2^{1+k/2}}{k!}=\frac2{\big(1\cdot3\cdot5\cdot\ldots\cdot(2m-1)\big)m!}<\frac2{(k/2)!^2}\;,$$ which is indeed much smaller than $1$ when $k$ is large. Only minor adjustments are required when $k$ is odd; I’ll leave them to you.

(1) is trivial as written: $0\le\lfloor 2^{k/2}\rfloor\le 2^{k/2}$ by the definition of floor and the fact that $2^{k/2}>0$, so $$0\le\frac{\lfloor 2^{k/2}\rfloor}{2^{k/2}}\le 1\;,$$ and therefore $$0\le\left(\frac{\lfloor 2^{k/2}\rfloor}{2^{k/2}}\right)^k\le 1\;.$$

If instead $n=2^{\lfloor k/2\rfloor}$, we have $0<2^{\lfloor k/2\rfloor}\le2^{k/2}$, and the same reasoning applies.

| cite | improve this answer | |
$\endgroup$

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.