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!
7
$\begingroup$
$\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$
$\endgroup$
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.
