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.
answered Apr 20 at 14:32
-
$\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 at 18:12
-
$\begingroup$ Then how is $n+{n\over 2}+{n\over 4}+...+2+1\lt n + n=2n$? $\endgroup$ – miniparser Sep 2 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$ – Yuval Filmus Sep 2 at 10:07
-
$\begingroup$ The OP implicitly assumes that $n$ is a power of 2. $\endgroup$ – Yuval Filmus Sep 2 at 10:07
