Discussion:
Vollständige Induktion - Hilfe bei einem Beweis
(zu alt für eine Antwort)
Udo
2017-04-04 08:32:39 UTC
Permalink
Raw Message
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
2017-04-04 10:34:33 UTC
Permalink
Raw Message
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
2017-04-04 11:20:11 UTC
Permalink
Raw Message
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
2017-04-04 15:27:02 UTC
Permalink
Raw Message
...
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
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Hans-Peter Diettrich
2017-04-04 13:15:25 UTC
Permalink
Raw Message
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
2017-04-05 05:53:22 UTC
Permalink
Raw Message
Danke für die Hilfe!
Grüße
Udo

Loading...