Asymptotik Frage

Ist $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$ ?

Ich stecke wirklich fest und glaube, dass es wahr ist, aber ich weiß nicht, wie ich es beweisen soll.

Jede Hilfe wäre dankbar!

asymptotics factorial big-o-notation Dudi Frid
quelle

Was haben Sie versucht, um es zu beweisen? Haben Sie versucht, die Definition von Big O oder Limits zu verwenden?

Ryan

Der Nenner ist nicht klar. ist es ? ist es ?

2! * 4! * 6! . . .

$2!*4!*6!...$

2! * 4! * 8! * 16! . . .

$2!*4!*8!*16!...$

Lox

Tnx, ich habe meine Frage bearbeitet

Dudi Frid

So scheint es zu sein

n - 2

$n-2$ Begriffe auf dem Nenner. Können Sie jeden dieser Begriffe mit einem Begriff im Zähler koppeln, der größer oder gleich diesem ist? Zum Beispiel der letzte

n / 2

$n/2$ Begriffe in

(n / 2)!

$(n/2)!$ würde sich mit dem letzten paaren

n / 2

$n/2$ Begriffe in

n!

$n!$ im Zähler und aufheben. Versuchen Sie dies mit dem ganzen Nenner.

Ryan

Könnten Sie bitte Ihre Antwort näher erläutern? Und beweisen oder widerlegen Sie es?

Dudi Frid

Antworten:

Wir haben Mit Stirlings Näherung können wir verfeinerte Asymptotik erhalten, aber wir überlassen dies dem interessierten Leser.

\frac{n!}{(n /. 2)! (n /. 4)! \dots 2!} = \frac{n!}{(n /. 2)! (n /. 2)!} \frac{(n /. 2)!}{(n /. 4)! (n /. 4)!} \dots \frac{4!}{2! 2!} \frac{2!}{1! 1!} = (\binom{n}{n /. 2}) (\binom{n /. 2}{n /. 4}) \dots (\binom{4}{2}) (\binom{2}{1}) \leq 2^{n} 2^{n /. 2} \dots 2^{4} 2^{2} = 2^{n + n /. 2 + \dots + 2 + 1} < 2^{2 n} = 4^{n} .

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

Yuval Filmus
quelle

Wie beweise ich ? Und was ist, wenn keine Potenz von ?

\frac{n}{2} + \frac{n}{4} + . . . + 2 + 1 < n

${n\over 2}+{n\over 4}+...+2+1\lt n$

n

$n$

2

$2$

Miniparser

Wie ist dann ?

n + \frac{n}{2} + \frac{n}{4} + . . . + 2 + 1 < n + n = 2 n

$n+{n\over 2}+{n\over 4}+...+2+1\lt n + n=2n$

Miniparser

Mein vorheriger Kommentar war falsch. Wir haben .

n + n / 2 + n / 4 + \dots + 1 = n (1 + 1 / 2 + 1 / 4 + \dots + 1 / n) \leq n \sum_{i = 0}^{\infty} 2^{- i} = 2 n

$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

Das OP geht implizit davon aus, dass eine Potenz von 2 ist.

n

$n$

Yuval Filmus