Verständnisproblem Vollständige Induktion

Hallo !

Ich verstehe das Bsp. zur Vollständigen Induktion nicht:

Zu Zeigen ist, dass für alle n € N, n <= 3 gilt:

2^n > n+2

(Lösung von Buch)

Voraussetzung: 2^n > 2+n

Dann wird mit 2 Multipliziert:

2 * 2^n = 2^(n+1) < 2(n + 2) = 2n + 4 >= n + 4 >= (n+1) + 2

Warum lässt man bei diesem Schritt einfach den Koeffizienten von n weg ?
2n + 4 >= n + 4

Danke im voraus!

Das Ziel ist, zu zeigen, dass:

2^(n+1) > (n+1)+2

, wobei du für dieses eine n≥3 voraussetzt, dass die Induktionsvoraussetzung (IV) 2^n > n+2 bereits gilt. Genau das haben die hier gemacht, nach anwenden der (IV) kommt eben heraus, dass 2^(n+1) sogar größer ist als 2n+4, du brauchst aber nur, dass es größer ist als n+3. 2n+4 ist aber logischerweise größer als n+3, also schätzt du größzügig ab, streichst ein n und eine 1 raus, und es steht da.

Ahhh, danke wußte nicht das man das einfach so machen kann.

Eine blöde Frage hab ich trotzdem noch, man soll ja die Aussage für n+1 überprüfen, warum setzt man dann nicht gleich statt n n+1 ein also so:

2^(n+1) > (n+1) + 2

Weil man über einen anderen Weg zu dem Ergebnis kommen muss um zu Beweisen das es stimmt ??

Irgendwie fehlt mir glaub ich noch der durchblick wie man da am Besten rangeht, bei dem Bsp. wurde einfach mit 2 multipliziert (damit der exponent zu n+1 wird, is mir schon klar), nur wie kommt man bei komplexeren Aussagen darauf was man machen muss.

Grossmeister

Gast46746 schrieb:

2 * 2^n = 2^(n+1) < 2(n + 2) = 2n + 4 >= n + 4 >= (n+1) + 2

Die Zeile ist für den Beweis zwecklos, weil du einmal nach oben, dann aber nach unten abschätzt. Oder war das ein Schreibfehler?

Grossmeister schrieb:

Gast46746 schrieb:

2 * 2^n = 2^(n+1) < 2(n + 2) = 2n + 4 >= n + 4 >= (n+1) + 2

Die Zeile ist für den Beweis zwecklos, weil du einmal nach oben, dann aber nach unten abschätzt. Oder war das ein Schreibfehler?

Tschuldigung habe mich vertippt, es sollte ">" sein nicht "<"

Also 2^(n+1) > 2(n+2) ...

Gast124 schrieb:

Irgendwie fehlt mir glaub ich noch der durchblick wie man da am Besten rangeht, bei dem Bsp. wurde einfach mit 2 multipliziert (damit der exponent zu n+1 wird, is mir schon klar), nur wie kommt man bei komplexeren Aussagen darauf was man machen muss.

Ich versteh auch nicht was das mit "mit 2 multiplizieren" soll. Uns hat man die vollständige Induktion damals so beigebracht:

Behauptung: Die Aussage 2^n > n+2 gilt für alle n ≥ 3.

Beweis per vollständiger Induktion:

Induktionsanfang (IA):
z.Z.: Die Aussage gilt für n=3: 2^3 = 8 > 3+2 = 5. Passt.

Induktionsschritt (IS):
Die Aussage 2^n > n+2 gelte für ein festes aber beliebiges n ≥ 3. Das ist die Induktionsvoraussetzung (IV).
z.Z.: Die Aussage gilt dann auch für n+1, also z.Z.: 2^(n+1) > n+3.
Das macht man immer indem man es auf die IV zurückführt:
2^(n+1) = 2 * 2^n
Nun kannst du die IV anwenden:
2 * 2^n > 2 * (n+2) = 2n+4 > (n+1)+2.

Nach dem Beweisprinzip der vollst...blabla. q.e.d.

asdfasdf von oben schrieb:

Gast124 schrieb:

Irgendwie fehlt mir glaub ich noch der durchblick wie man da am Besten rangeht, bei dem Bsp. wurde einfach mit 2 multipliziert (damit der exponent zu n+1 wird, is mir schon klar), nur wie kommt man bei komplexeren Aussagen darauf was man machen muss.

Ich versteh auch nicht was das mit "mit 2 multiplizieren" soll. Uns hat man die vollständige Induktion damals so beigebracht:

Behauptung: Die Aussage 2^n > n+2 gilt für alle n ≥ 3.

Beweis per vollständiger Induktion:

Induktionsanfang (IA):
z.Z.: Die Aussage gilt für n=3: 2^3 = 8 > 3+2 = 5. Passt.

Induktionsschritt (IS):
Die Aussage 2^n > n+2 gelte für ein festes aber beliebiges n ≥ 3. Das ist die Induktionsvoraussetzung (IV).
z.Z.: Die Aussage gilt dann auch für n+1, also z.Z.: 2^(n+1) > n+3.
Das macht man immer indem man es auf die IV zurückführt:
2^(n+1) = 2 * 2^n
Nun kannst du die IV anwenden:
2 * 2^n > 2 * (n+2) = 2n+4 > (n+1)+2.

Nach dem Beweisprinzip der vollst...blabla. q.e.d.

Ja, das hab ich vorhin falsch versatnden, weil im Buch steht "Multipliziert man mit 2 so ergibt sich direkt..."

Hab ein paar Beispiele gerechnet und es klappt ich verstehs jetzt endlich.

Der Gedanke des zurückführens hat mir gefehlt

danke !

SG1

asdfasdf von oben schrieb:

z.Z.: Die Aussage gilt für n=3: 2^3 = 8 > 3+2 = 5. Passt.

Kann mir eigentlich mal wer erklären, warum so viele Leute das genau so schreiben? Ich hätte das jetzt geschrieben als

2^3 = 8 > 5 = 3+2

und verstehe das als Kurzform von

2^3 = 8 und 8 > 5 und 5 = 3+2, also ist 2^3 > 3+2

Wie soll ich die oben zitierte Zeile dann verstehen? 8 > 3+2 ist
* eine unbewiesene Behauptung
* für den Beweis irrelevant.

Oder werden hier ganze Gleichungen miteinander verglichen?
(2^3 = > (3+2 = 5)?