Induktion: Wie funktioniert hier der Beweis?

Question

Guten Tag zusammen

Ich habe eine Frage zur Induktion.

Aufgabe: M ist eine endliche Menge mit n Elementen: |M| = n. Wir wissen, dass für die Potenzmenge P(M) gilt: |P(M)| = 2ⁿ

Beweisen Sie mit vollständiger Induktion, dass P(n) : n < 2ⁿ für alle n Element von N gilt. (P(n) bedeutet ein Prädikat. Sie dürfen voraussetzen, dass 1 <= 2ⁿ für alle n Element von N gilt.

Meine Lösung:

Induktionsschritt:

P(k) : k < 2^k

P(k+1) : k+1 < 2^k+1

Wie beweise ich das jetzt?

Mein Vorschlag P(k+1) in P(k) einsetzen

k + 1 (da bei P(k+1) eine Zahl hinzugekommen ist) < 2^k (Wie mache ich hier das? ich müsste ja dann bei 2k plus 1 schreiben, dann hätten wir: 2^k+1)

Lösung von meinem Lehrer:

k+1 < 2^k + 1                <-- Was soll das +1 sein?

k+1 < 2^k +2^k = 2 * 2^k = 2^k+1d    <-- Wie kommt er auf 2^k + 2^k

Kann mir hier jemand helfen?

Vielen Dank im Voraus!

LG
Apple

Answer 1

k + 1 < k + k = 2·k < 2·2^k = 2^k+1.

Was soll das +1 sein?

Man darf in der Ungleichung

        k < 2^k

auf beiden Seiten 1 addieren. Warum das zieführend ist, stellt sich später heraus.

Wie kommt er auf 2^k + 2^k

Man darf in der Ungleichung

        k+1 < 2^k + 1

die 1 auf der rechten Seite durch etwas ersetzen, was größer als 1 ist. 2^k ist größer als 1.

Comments

Guten Tag oswald

Danke vielmals für Ihre Hilfe. Mir stellt sich jedoch hier noch die Frage:

- Hat das +1 nichts mit P(k+1) zu tun?

- Warum hat er sich für das Ersetzen von 1 mit 2^k entschieden? Man könnte ja auch einfach 2 nehmen.

Ich verstehe in diesem Beispiel den Sinn des Induktionsschrittes gar nicht. Mir fehlt hier der Beweis P(k) → P(k+1).

Vielen Dank im Voraus!

LG
Apple

---

- Hat das +1 nichts mit P(k+1) zu tun?

Doch, hat es.

- Warum hat er sich für das Ersetzen von 1 mit 2^k entschieden? Man könnte ja auch einfach 2 nehmen.

Weil die rechte Seite der Ungleichung dann zu 2^k+1 umgeform werden kann.

Mir fehlt hier der Beweis P(k) → P(k+1).

Die Lösung deines Lehrers besagt im Wesentlichen:

        Wenn k < 2^k ist, dann ist

                k+1 < 2^k+1

     und somit

               k+1 < 2^k+1.