Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?

I am really stuck and I tend to believe it's true, but I don't know how to prove it.

Any help would be appreciated!

  • 1
    $\begingroup$ What have you tried in proving it? Have you tried using definition of big O or limits? $\endgroup$
    – ryan
    Apr 20 '19 at 14:12
  • 2
    $\begingroup$ the denominator is not clear. is it $2!*4!*6!...$? is it $2!*4!*8!*16!...$? $\endgroup$
    – lox
    Apr 20 '19 at 14:12
  • $\begingroup$ Tnx, I edited my question $\endgroup$
    – Dudi Frid
    Apr 20 '19 at 14:14
  • $\begingroup$ So it appears there will be $n-2$ terms on the denominator. Can you pair up each of these terms with a term in the numerator that is greater than or equal to it? For instance, the last $n/2$ terms in $(n/2)!$ would pairs up with the last $n/2$ terms in $n!$ in the numerator and cancel out. Try this with the whole denominator. $\endgroup$
    – ryan
    Apr 20 '19 at 14:23
  • $\begingroup$ Could you please elaborate on your answer? And do you prove or disprove it? $\endgroup$
    – Dudi Frid
    Apr 20 '19 at 14:26

We have $$ \frac{n!}{(n/2)!(n/4)!\cdots 2!} = \frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\ \binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n. $$ Using Stirling's approximation we can get more refined asymptotics, but we leave this to the interested reader.

  • $\begingroup$ How to prove ${n\over 2}+{n\over 4}+...+2+1\lt n$? And what if $n$ is not a power of $2$? $\endgroup$
    – miniparser
    Sep 1 '19 at 18:12
  • $\begingroup$ Then how is $n+{n\over 2}+{n\over 4}+...+2+1\lt n + n=2n$? $\endgroup$
    – miniparser
    Sep 2 '19 at 9:20
  • $\begingroup$ My previous comment was mistaken. We have $n + n/2 + n/4 + \cdots + 1 = n(1 + 1/2+1/4 + \cdots + 1/n) \leq n\sum_{i=0}^\infty 2^{-i} = 2n$. $\endgroup$ Sep 2 '19 at 10:07
  • $\begingroup$ The OP implicitly assumes that $n$ is a power of 2. $\endgroup$ Sep 2 '19 at 10:07

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.