(Starke) Induktion : n! > 2^n

08.11.2015, 15:50	jns135	Auf diesen Beitrag antworten »
(Starke) Induktion : n! > 2^n Meine Frage: Hallo Leute, ich stehe gerade vor der folgenden Aufgabe: Beweisen Sie mittels vollständiger oder starker Induktion: Für alle n aus den Natürlichen Zahlen, n >= 4 gilt: n! > 2^n Könnte mir zunächst einmal jemand den Unterschied zwischen vollständiger und starker Induktion erklären? Sehe ich das richtig, dass sich starke Induktion für Beweise eignet, bei denen n nicht jedes beliebige Element aus N sein kann, sondern durch ein n >= x oder <= x eingeschränkt wird? Meine Ideen: Meine bisherigen Ansätze: Induktionsanfang: n = 4 4! > 2^4 4 * 3 * 2 * 1 > 2^4 24 > 16 Induktionsschritt : A(n) -> n+1 (n+1)! > 2^(n+1) => (n+1) * n! > 2 * 2^n Diese Aussage ist offensichtlich wahr, so lange (n+1) auf der linken Seite größer ist als der Faktor 2 auf der rechten seite. Da n >= 4, wächst die linke Seite also deutlich schneller als die rechte und ist dementsprechend für alle n >= 4 auch größer. Meine Frage ist nun, wie ich das vernünftig mathematisch aufschreibe.
08.11.2015, 16:29	Mi_cha	Auf diesen Beitrag antworten »
deine Überlegungen sind richtig. Ordentlich sähe das etwa so aus: IV: $\begin{eqnarray} n=4: \end{eqnarray}$ $\begin{eqnarray} [4! > 2^4 \end{eqnarray}$ $\begin{eqnarray} 24 > 16 \end{eqnarray}$ stimmt IS: $\begin{eqnarray} n \xrightarrow\ n+1 \end{eqnarray}$ $\begin{eqnarray} (n+1)! = n! \cdot (n+1) \end{eqnarray}$ $\begin{eqnarray} > 2^n\cdot (n+1) \end{eqnarray}$ nach Voraussetzung $\begin{eqnarray} > 2^n\cdot 2 \end{eqnarray}$ da hier 2<n+1, $\begin{eqnarray} =2^{n+1} \end{eqnarray}$
08.11.2015, 16:58	jns135	Auf diesen Beitrag antworten »
Danke vielmals für die Antwort. Könntest du noch etwas zu starke Induktion vs. vollständige Induktion sagen?
08.11.2015, 17:06	Mi_cha	Auf diesen Beitrag antworten »
starke Induktion habe ich vorher noch nicht gehört, daher kann ich nicht viel dazu sagen. Vielleicht hilft das
08.11.2015, 17:27	jns135	Auf diesen Beitrag antworten »
ja, das Skript hatte ich vorher auch gefunden und es sieht auch ähnlich aus wie das Skript meines Profs. Allerdings finde ich, dass bei beiden Verfahren mehr oder weniger das gleiche steht, nur dass die starke Induktion annimmt, dass es schon mehrere Induktionsanfänge gibt (?). Im Endeffekt geht es aber darum, die Gültigkeit für n+1 zu zeigen. Nochmals Danke für deine Hilfe.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »