Vollständige Induktion - Hilfe bei einem Beweis

[Udo]

Hallo,

in einem Lehrbuch fand ich folgende Übungsaufgabe, bei der ich mich irgendwie dumm angestellt habe:

Beweisen Sie über vollständige Induktion, dass gilt
2*n ≤ 2^n für n ∊ ℕ

Also zeige ich

(1) Gültigkeit für n=1: 2*1 = 2^1 ist OK.
(2) Die Ungleichung gelte für irgendein k (Induktionsannahme)

2*k ≤ 2^k

(3) Für (k+1) gilt dann, von der rechten Seite ausgehend

2^(k+1) = 2^k * 2

Und mit der Induktionsannahme (2^k ≥ 2*k) wird die rechte Seite kleiner,
wenn ich 2^k durch 2*k ersetze, also

2^(k+1) ≥ 2*k *2
2^(k+1) ≥ 4*k
2^(k+1) ≥ 2k + 2k
2^(k+1) ≥ 2(k + 2)

Da k > 0 und k ∊ ℕ wird die rechte Seite noch kleiner, wenn ich statt
(k+2) den Term (k+1) setze.

Also:

2^(k+1) ≥ 2(k +1)

was sich auch ergibt, wenn ich (k+1) in die Ungleichung bei (2)
direkt einsetze.

Ist diese Beweisführung mathematisch korrekt? Darf man so argumentieren oder mache ich da irgendwo einen Fehler?
(Mir kommt der Schritt, wo ich (k+2) einfach durch (k+1) ersetze irgendwie nicht ganz geheuer vor).

Danke und Grüße
Udo

[Hans-Peter Diettrich]

Post by Udo
Beweisen Sie über vollständige Induktion, dass gilt
2*n ≤ 2^n für n ∊ ℕ
2^(k+1) ≥ 2k + 2k
2^(k+1) ≥ 2(k + 2)

In diesem letzten Schritt komme ich richtig ausgeklammert auf
2^(k+1) >= 2*(2*k) //nicht k+2
und daraus
2*2^k >= 2*2*k
und gekürzt
2^k >= 2*k
was laut Induktionsannahme stimmt.

Rechne das nochmal nach, vermutlich hast Du Dich da nur einmal beim
Rechnen verhauen.

DoDi

[Udo]

Post by Hans-Peter Diettrich
...
In diesem letzten Schritt komme ich richtig ausgeklammert auf
2^(k+1) >= 2*(2*k) //nicht k+2

Oh Mann, rechnen sollte man können ...
Danke für den Hinweis.

Also, bis zum Schritt 2^(k+1) ≥ 2k + 2k
war's richtig.
Könnte ich jetzt folgendermaßen argumentieren?
Wenn schon gilt 2^(k+1) ≥ 2k + 2k
dann wird die rechte Seite ja noch kleiner, wenn ich für k den
kleinstmöglichen Wert k=1 einsetze.

Dann steht da:
2^(k+1) ≥ 2k + 2k
2^(k+1) ≥ 2k + 2*1
2^(k+1) ≥ 2(k + 1) und ich hätte meinen Beweis gerettet.

Darf ich so argumentieren?
Grüße
Udo

[Detlef Müller]

...

Post by Udo
Wenn schon gilt 2^(k+1) ≥ 2k + 2k
dann wird die rechte Seite ja noch kleiner, wenn ich für k den
kleinstmöglichen Wert k=1 einsetze.
2^(k+1) ≥ 2k + 2k
2^(k+1) ≥ 2k + 2*1
2^(k+1) ≥ 2(k + 1) und ich hätte meinen Beweis gerettet.
Darf ich so argumentieren?

Warum nicht?

Wobei ich es klarer finde, gleich eine Ungleichungskette mit
Erläuterungen hin zu schreiben, also

2^(k+1) = 2 (2^k) | 2^k ≥ 2k nach IV
≥ 2 (2k) |
= 2k + 2k | k ≥ 1
≥ 2k + 2*1 | ausklammern.
≥ 2(k + 1)

Zusammen also

2^(k+1) ≥ 2(k + 1)

Gruß,
Detlef

[Hans-Peter Diettrich]

Post by Udo
Ist diese Beweisführung mathematisch korrekt? Darf man so argumentieren oder mache ich da irgendwo einen Fehler?
(Mir kommt der Schritt, wo ich (k+2) einfach durch (k+1) ersetze irgendwie nicht ganz geheuer vor).

Da muß wohl ein gestandener Mathematiker her, um die Zulässigkeit Deiner
Umformungen zu beurteilen.

DoDi

[Udo]

Danke für die Hilfe!
Grüße
Udo