# Asymptotics question

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!

• What have you tried in proving it? Have you tried using definition of big O or limits? – ryan Apr 20 at 14:12
• the denominator is not clear. is it $2!*4!*6!...$? is it $2!*4!*8!*16!...$? – lox Apr 20 at 14:12
• Tnx, I edited my question – Dudi Frid Apr 20 at 14:14
• 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. – ryan Apr 20 at 14:23
• Could you please elaborate on your answer? And do you prove or disprove it? – Dudi Frid Apr 20 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.