Vollständige Induktion: Beweise die Annahme 2^{n} > n + 2, wobei gilt n ≥ 3

Question

Aufgabe:

Vollständige Induktion: Es sei gegeben die Annahme $$2^{n} > n + 2 $$ Wobei gilt: n ≥ 3. Beweisen Sie dies mit vollständiger Induktion.

Problem/Ansatz:

1. Induktionsanfang: 2^(3) > 3 + 2 => wahr

2. Induktionsannahme(behauptung)& Voraussetzung: Es gelte 2^{n} > n + 2 , solange n >= 3

3. Induktionsschritt lt. Lösung: (die ich leider nicht verstehe)

$$2^{n} > n + 2 $$

$$2 * 2 ^{n} = 2 ^{n+1} > 2(n+2) = 2n + 4 >= n+ 4 >= (n+1)+2 $$

Bei der Induktion wird also n + 1, das nächstfolgende Element geprüft, damit dies für alle natürlichen Zahlen gelte. Weshalb aber dann 2 * 2^{n} (ist wahrscheinlich dasselbe wie 2^{n+1}, daher logisch, aber wenn man mit 2 multipliziert, geht man ja immer noch nicht von n >= 3 aus ? Und was mir vollends unklar ist: warum aus 2*n + 4 >= n +4 (Vorgänger ok) >= (n+1) + 2 (vollkommen unklar, kann kein Vorgänger sein)

Anm.: , bin ein vollkommener Neuling im Bereich der höheren Mathematik, nur mein Problem ist, jetzt stundenlang über dieses Beispiel nachzudenken, hilft mir leider nicht weiter, und ohne dies zu verstehen, durchbreche ich auch nicht wirklich die Schranke der Logik und kann mich nicht weiterentwickeln, daher würde ich euch bitten, mir dieses Beispiel verständlich zu machen und dann ev. folgend die Logik dahinter etwas besser zu verstehen, um zukünftige Beispiele besser meistern zu können. Vielen lieben Dank :)

Answer 1

Ich hoffe, ich kann dir das hiermit etwas deutlicher machen:

Die vollständige Induktion im Allgemeinen funktioniert wie folgt:
Wir zeigen, dass unsere zu beweisende Aussage für ein beliebig festes \(n\in\mathbb{N}\) wahr ist. (Normalerweise wird das kleinstmögliche \(n\) genommen, für das die Gleichung gilt). Danach zeigen wir, dass die Aussage dann auch für jeden beliebigen, festen Nachfolger \(n+1\) gilt.

Mithilfe der Metapher der Dominosteine kann man sich die Aussagen wie folgt vorstellen:
Nehmen wir an, dass wir die folgende Dominoreihe in Anlehnung an die Ungleichung des Fragestellers gegeben haben: \(D_3,D_4,D_5, D_6, D_7, D_8,\ldots \)

Die vollständige Induktion über \(n=3,4,5,6,7,8,\ldots\) macht folgende Aussagen über die Steine:

1. Der kleinstmögliche Stein - also \(D_3\) fällt um (Induktionsanfang)
2. Wenn der \(n\)-te Stein umfällt, dann auch der \(n+1\)-te Stein (Induktionsschritt)

Wir wissen wegen (I), dass Stein \(D_3\) umfällt. Weil \(D_3\) umfällt, gibt es ein \(n\), für das ein Stein umfällt. Demnach fällt auch wegen (II) der Nachfolger \((n+1)\) um, d.h. \(D_4\) wird auch umgeworfen. Weil \(D_4\) aber umgeworfen wurde, wird wegen (II) auch \(D_5\) umfallen usw. usf.. Diese Kette kann man unendlich fortführen und die gesamte Dominoreihe wird umfallen, d.h. wir haben die Aussage für alle natürlichen Zahlen \(n\) bewiesen.

Gucken wir uns jetzt dein Beispiel an:

Induktionsanfang (IA): Wählen \(n=3\). Also muss \(8>5\;\checkmark\) gelten, stimmt.
Induktionsvoraussetzung (IV): Es gilt \(2^n>n+2\) für ein beliebig festes \(n\geq 3\) aus den natürlichen Zahlen, was wir in der IA gezeigt haben.
Induktionsbehauptung (IB): Wir behaupten \(2^{n+1}>(n+1)+2\) für alle \(n\geq 3\) mit \(n\in\mathbb{N}\).
Induktionsschritt: Wir beweisen IB wie folgt:
$$\begin{aligned} 2^{n+1} = 2^{n}+2^{n}&\stackrel{IV}{>}n+2 + n+2\\ &= 2n+4\\ &>n+4\\ &>(n+1)+2\quad \checkmark \end{aligned}$$ Damit ist die IB bewiesen und die Ungleichung gilt für alle \(n\geq3,\; n\in\mathbb{N}\)

Wir schätzen \(2n+4>n+4>(n+1)+2\) ab, um auf die gewünschte Form \((n+1)+2\) zu kommen und somit die Ungleichung als wahr zu beweisen.

Es gibt natürlich einen Spielraum bei Abschätzungen: Zum Lösen eines Problems muss es nicht nur eine richtige Abschätzung geben, es können auch andere Abschätzungen zum Ziel führen, z.B.: \(2n+4>n+n>(n+1)+2\).
Jedoch gibt es auch Beispiele, die uns nicht zum richtigen Ergebnis führen: \(2n+4>0\) wäre eine Abschätzung mit der die Ungleichung nicht bewiesen werden könnte.

Falls du einzelne Schritte noch nicht verstehst, sag Bescheid. Ich werde dir das gerne noch erklären!

Comments

Es ist mir zwar peinlich, aber am Anfang ist es oftmals schwierig die Logikschranke zu durchbrechen, allgemein verstehe ich natürlich den Induktionsanfang, die Induktionsvoraussetzung und die -behauptung.

Den Induktionsschritt verstehe ich grundlegend auch, womit ich nur Probleme habe, allgemein wird gesagt n + 1 , d.h. in dem Fall 2^(n) * 2 ,( n + 2) * 2 , was ich leider überhaupt nicht verstehe und da bleib ich hängen ist die Umformung 2 n + 4 > n + 4 (warum? und steht das im Zusammenhang mit 2^(n +1 ) oder mit (2n + 4), wird bewiesen, dass 2n + 4 > n + 4 ist ? (Ist ja grundsätzlich logisch, nur ich könnte ja auch sagen 2n + 4 > 4n + 3 ? Und weshalb dann (n + 1) + 2 und v.a. wieso wird das in der Form gelöst, um Herauszufinden, dass 2^(n) + 2^(n> größer ist als (n+2) - das ist das Problem, das ich nicht verstehe.

Also entschuldigung, dass ich dich mit so viel konfrontiere, aber aller Anfang ist schwer.. :)

Danke aufjedenfall schon mal für deine Antwort :-)

/*****/

Edit.: 2n+4 (was wäre, wenn man 1 einsetzen würde, v. niedrigst effektiven ausginge? dann wäre d. 6, dann wäre n + 4 = 5 (6> 5) , dann wäre das letzte 4 -> 6>=5>=4 (so könnte ich es mir erklären), aber selbst wenn diese Weise des Denkens richtig sei, weshalb, was beweist man damit, warum wird das so bewiesen, wie steht das im Zusammenhang mit 2^(n), was muss ich machen, um derartig schemantisch-logische-algebraische Strukturen zu durchschauen?

---

Wir schätzen nach unten ab, um dann auf die Form der anderen Ungleichungsseite zu kommen. Wir möchten ja zeigen, dass \(2^{n+1}>(n+1)+2\) gilt. Dafür formen wir \(2^{n+1}\) so lange um und setzen die Voraussetzung ein, bis wir auf die andere Seite kommen und damit die Gültigkeit der Ungleichung bewiesen haben. Deshalb helfen uns die Abschätzungen \(2n+4>n+4>n+2+1\) weiter, weil uns das genau auf den Term auf der rechten Seite bringt.

Klar könnte man auch \(2n+4>0\) abschätzen, aber das würde hier nicht zum Ergebnis führen. Deine alternative Abschätzung von \(2n+4\stackrel{!}{>}4n+3\) ist übrigens falsch, weil dies für keine \(n\) aus den natürlichen Zahlen gilt.

---

Den Sinn der vollständigen Induktion kann man mithilfe einer Dominosteinreihe gut erklären: Wenn wir einen Dominostein umwerfen (Induktionsanfang, daraus leiten wir Induktionvoraussetzung ab, also Aussage stimmt für ein n) und dann auch zeigen können, dass der darauffolgende Dominostein auch umfällt (Induktionsbehauptung und Beweis im Induktionsschritt), weiß man, dass der darauffolgende auch umfällt und der darauffolgende auch usw. Man beweist also damit, dass die Aussage für alle \(n\in\mathbb{N}\) gilt.

Das wird hier bei Wikipedia nochmal gut erklärt im Teil "Veranschaulichung": https://de.wikipedia.org/wiki/Vollst%C3%A4ndige_Induktion

---

Da braucht dir im Übrigen auch nichts peinlich sein. Jeder hat bei neuen Konzepten Probleme und dann ist es doch gerade gut, wenn man bestimmte Gedankenwege anderer Menschen probiert zu verstehen und bei Unklarheiten nachhakt!

"Wer fragt, ist ein Narr für eine Minute. Wer nicht fragt, ist ein Narr sein Leben lang."

---

Ok, vielen Dank schon Mal für deine Bemühungen, ist es normal, dass in dem Fall aller Anfang schwer ist? Verstehe meistens schon das meiste, nur wenn, es partout nicht sein will... Klar, morgen fängt erst die 1. Vorlesung an, und vielleicht wird das eine oder andere noch erklärt, sodass es jeder versteht, hab nur jetzt schon das Buch des 1. Semesters gelesen, um Schwächen vorzeitig abzuklären, und die Möglichkeit durchzufallen zumindest ein wenig zu verringern.

Soweit ich es jetzt verstanden habe:

2^(n+1) > (n + 1 ) + 2 (soll bewiesen werden)

Das erreicht man, indem man mit 2 multipliziert

2 * 2^(n) = 2^(n + 1) > (n + 2) *2 (zweimal das ist aber nicht n + 1 + 2 , es geht aber um 2^(n), und wenn man bei dem n + 1 rechnet, müsste man 2^(n) * 2 sagen, das heißt man muss auch die andere Seite Mal zwei rechnen (Äquivalenzprinzip) , da nun 2^(n + 1 ) > 2^(n + 2 ), gilt auch 2^(n + 1) > n + 2 + 1 , was bewiesen hätte werden sein müssen :), weil gilt verschobener Anfang zu n + 3 (wenn n = 0, dann gilt trotzdem n >= 3 ) - hoffe dass ich es jetzt soweit verstanden habe, sofern meine Herleitungen richtig sind, natürlich.

Nichtsdestotrotz hoffe ich es und danke dir für deine Antwort :) - Wenn jedoch jedes Beispiel so schwer wird.. ja.. aber irgendwann durchschaut man die Logik dann wirklich, hoffentlich :D

Edit: solltes es aber anders zu interpretieren sein, gelte ja der Beweis wieder nicht, dass 2^(n + 1 ) > n + 1 + 2 ist, sofern man 1 oder 2 einsetzt gilt diese Ungleichung ja wieder nicht? oder?

---

Ja, das ist normal. Deine Vorlesungen haben ja noch nicht Mal begonnen und du versuchst schon den Stoff dir anzueignen, was wirklich sehr gut und vorbildlich ist. Dadurch hast du einen enormen Vorsprung gegenüber deinen Kommilitonen. Aber da ist es ja klar, dass man Mal was nicht versteht. Man hat ja schließlich noch keine Übungen und Vorlesungen mit Erklärungen und eklärenden Beispielen gesehen. Also mache dir bloß keinen Kopf, du bist auf einem guten Weg das alles zu verstehen, wenn du weiter so an der Sache dranbleibst!

Du möchtest 2^n > n+2 beweisen. Dafür zeigst du, dass die Ungleichung für ein bestimmtes n gilt. Danach zeigst du, dass sie auch für jeden Nachfolger gilt, also du zeigst, dass 2^(n+1)>(n+1)+2 ist für n>=3. Wenn letzteres gilt, dann gilt die Gleichung 2^n>n+2 für alle n>=3, weil sie für n und jeden Nachfolger n+1 gilt. Du schließt also von 3 auf 4, von 4 auf 5, von 5 auf 6, usw... Ist das verständlich?

Die (Un-)Gleichung 2*2^(n)=2^n+2^n>(n+2)*2 rührt nicht aus dem Multipizieren beider Seiten mit 2, sondern vielmehr aus der Induktionsvoraussetzung: In der IV steht, dass 2^n>n+2 für ein festes n gilt. Das können wir jetzt einfach in die Ungleichung einsetzen: 2^n+2^n=n+2+n+2, also zwei Mal die Induktionsvoraussetzung eingesetzt.

2^(n+1) ist nicht größer als 2^(n+2): Gegenbeispiel: n=2 => 2^3=8 < 16 = 2^4

Sehr gerne!

Ja - natürlich nur für n>=3, habe ich berichtigt.

---

Video-Literatur in der das sehr ausführlich und anschaulich erklärt wird:

,

und

.

---

Ich habe meine Antwort um die "Dominometapher" in Anlehnung an das YouTube-Video erweitert und diese sollte das Konzept der Induktion sehr verständlich machen!