Zeige durch vollständige Induktion, dass n \cdot 2^n = O(n!)

Question

Hallo Leute,

Ich möchte zeigen, dass \(n \cdot 2^n = O(n!)\) mittels vollständiger Induktion gilt. Demnach muss man ja zeigen, dass es eine Konstante \(a > 0\) gibt und eine Zahl \(n_0\) gibt, sodass für alle \(n \geq n_0\) gilt: \(n \cdot 2^n \leq a \cdot n!\).

So weit so klar. Dazu habe ich dann das hier gemacht:

Induktionsanfang für n=1
- Links: \(1 \cdot 2^1 = 2\)
- Rechts: \(1! = 1\)

Es ist offensichtlich, dass \(2 \leq a \cdot 1!\) für eine Konstante \(a \geq 2\) stimmt. Daher gilt der Induktionsanfang für \(a = 2\).

Induktionsannahme
Nun gehen wir davon aus, dass die Aussage für ein beliebiges \(n \geq 1\) gilt, das heißt: \(n \cdot 2^n \leq a \cdot n!\)

Induktionsschritt
Nun müssen wir zeigen, dass die Aussage auch für \(n = n+1\) gilt, d. h. wir müssen zeigen, dass: \( (n+1) \cdot 2^{n+1} \leq a \cdot (n+1)! \)

Um dies zu beweisen, beginnen wir mit der linken Seite der Ungleichung:
\((n+1) \cdot 2^{n+1} =  (n+1) \cdot 2 \cdot 2^n = n \cdot 2^n \cdot 2 + 2^{n+1} \)

Und jetzt könnte man die Induktionsannahme einsetzen:
\( n \cdot 2^n \cdot 2 + 2^{n+1} \leq a \cdot n! \cdot 2 + 2^{n+1} \)

Aber leider weiß ich an dieser Stelle nicht, wie ich das lösen soll, und komme nicht weiter.

Comments

Die Wahl von \(a=2\) ist problematisch, denn für \(n=2\) und \(n=3\) muss \(a\) mindestens 4 sein, wenn du die Aussage für alle \(n\in\mathbb N\) zeigen willst.

Das heißt, für \(a=2\) kann dir der Induktionschritt nicht gelingen. Der Induktionschritt muss sogar ergeben, dass du eine Konstante \(a\geq 4\) wählen musst.

Answer 1

Hier hat man eine schönen Fall, bei dem der Induktionschritt zeigt, ab welchem \(n\) die Induktion tatsächlich funktioniert.

Man startet also mit einem unbekannten \(a\geq 2\) und schaut sich den Induktionsschritt genauer an.

Mit der Induktionvoraussetzung (IV) \(n2^n \leq an!\) ergibt sich:

$$(n+1)2^{n+1}=2n2^{n} + \underbrace{2\cdot 2^n}_{=\frac 2n\cdot n2^n }\stackrel{IV}{\leq}2an!+\frac 2n a n! = \color{blue}{\left(2+\frac 2n\right)an!}$$

Der Induktionsschritt gelingt, wenn

$${\color{blue}{\left(2+\frac 2n\right)an!}}\leq a(n+1)!$$

Damit erhalten wir eine Bedinung für \(n\):

$$2+\frac 2n \leq n+1 \Leftrightarrow 1+\frac 2n \leq n \Rightarrow \boxed{n\geq 2}$$

Die Induktion muss also bei \(n=2\) starten:

$$2\cdot 2^2 = 8 \leq a\cdot 2! \Rightarrow \boxed{a\geq 4}$$

Eigentlich bist du hier schon fertig, denn die Konstante \(a=4\) funktioniert für alle \(n\geq 2\).

Da \(a=4\) auch für \(n=1\) funktioniert, gilt die Ungleichung nun sogar für alle \(n\geq 1\).

Comments

Diese Überlegung würde ich insofern relativieren, dass ja eine direkte Abschätzung möglich ist: Für \(n \geq 3\) gilt:

$$\frac{n2^n}{n!}=n\; \frac{\prod_{j=1}^n 2}{\prod_{j=1}^n j}=4 \prod_{j=2}^{n-1}\frac{2}{j}\leq 4$$

Wo ein direkter Beweis möglich ist, ist immer auch in Induktionsbeweis möglich.

(Man sieht auch direkt, dass sogar "klein - o" gilt.)

Answer 2

Schreibe das übrige \(2^{n+1}=2\cdot 2^n\leq n\cdot 2^n\) und wende die IV noch einmal an.