# 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 '19 at 14:12
• the denominator is not clear. is it $2!*4!*6!...$? is it $2!*4!*8!*16!...$? – lox Apr 20 '19 at 14:12
• Tnx, I edited my question – Dudi Frid Apr 20 '19 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 '19 at 14:23
• Could you please elaborate on your answer? And do you prove or disprove it? – 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.
• How to prove ${n\over 2}+{n\over 4}+...+2+1\lt n$? And what if $n$ is not a power of $2$? – miniparser Sep 1 '19 at 18:12
• Then how is $n+{n\over 2}+{n\over 4}+...+2+1\lt n + n=2n$? – miniparser Sep 2 '19 at 9:20
• 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$. – Yuval Filmus Sep 2 '19 at 10:07
• The OP implicitly assumes that $n$ is a power of 2. – Yuval Filmus Sep 2 '19 at 10:07