7
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ What have you tried in proving it? Have you tried using definition of big O or limits? $\endgroup$ – ryan Apr 20 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 at 14:12
  • $\begingroup$ Tnx, I edited my question $\endgroup$ – Dudi Frid Apr 20 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 at 14:23
  • $\begingroup$ Could you please elaborate on your answer? And do you prove or disprove it? $\endgroup$ – Dudi Frid Apr 20 at 14:26
18
$\begingroup$

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.

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