Einstieg in ...   Mathematik, vollständige Induktion




5. Beispiel

Es folgt der Beweis einer Ungleichung. Zweckmäßig ist eine kleine Wiederholung vorweg.
Sollte hier etwas unklar sein, dann hilft das Internet weiter, z.B. Daniel Jung.

Ungleichungen sehen folgendermaßen aus:

\( x \leq{-4} \), das heißt x ist kleiner oder gleich -4. Lösungen für x wären -120, -6, -5 und auch -4.

\( x \geq{-4} \), das heißt x ist größer oder gleich -4. Lösungen für x wären 120, 6, -3 und auch -4.

\( x > -4 \), das heißt x ist größer als -4. Lösungen für x wären 120, 6, -3,175.

Wie auch bei Gleichungen können auf beiden Seiten Werte addiert oder subtrahiert werden.

Gegeben ist die Ungleichung \( x-8 < 3 \). Ein Addieren von acht auf beiden Seiten führt

zu der Lösung \( x < 11 \).

Multiplizieren und Dividieren sind ebenfalls möglich. Zu beachten ist:
wenn wir mit negativen Zahlen arbeiten, dann dreht sich das Relationszeichen.

\( 5 < 7 ~~~~ | *(-1) \) ergibt

\( -5 < -7 \) was aber falsch ist.

\( -5 > -7 \) nach Drehung von "<" zu ">" wieder richtig.

Gleiches gilt bei der Division mit einer negativen Zahl:

\( -8 < 2 ~~~~ | : (- \frac{1}{2}) \)

\( 16 < -4 \) ist falsch.

\( 16 > -4 \) jetzt richtig.


Übungsvorschlag: Sie potenzieren beide Seiten folgender Ungleichungen mit 2,3 und 4:

\( -3 < 4 \) und \( -3 < 2 \).

und untersuchen, wann das Relationszeichen gedreht werden muss.


Sie stehen vor dem Problem zu beweisen, dass gilt: \( a < h \).

Üblicherweise ist dieses nicht sofort ersichtlich, und Sie nehmen weitere Hilfsterme hinzu:

\( a < b < c < d < e < f < g < h \). Dann zeigen Sie nacheinander \( a < b \) ,

\( b < c \) , \( c < d \) , ... , \( g < h \). Dann ist \( a < h \) bewiesen.

Auch die Abfolge \( a = b = c = d < e = f = g = h \) würde ausreichen.

Nicht ausreichend wäre \( a \leq{b} \leq{c} \leq{d} \leq{e} \leq{f} \leq{g} \leq{h} \).

Für den Beweis \( a \leq{h} \) ist \( a = b = c = d = e = f = g = h \) ausreichend.

Sobald in der Kette ein \( \geq \) oder gar ">" erscheint, ist keine Aussage möglich.

Also \( a \leq{h} \) ist nicht bewiesen durch die Kette \( a < b < c < d < e < f \geq g < h \).

Wir sprechen von einer Abschätzung, wenn wir z.B. \( g\leq{h} \) schreiben und dieses auch für einen

oder mehrere Werte beweisen können. g nennt man dann untere Abschätzung für h.

Eine Abschätzung darf eine unpräzise Aussage sein, muss aber stets richtig sein.

Gegeben ist die wahre Aussage 10 < 20 <30 < 40 < 50 < 60.
Ebenfalls richtig ist 10 < 20 < 39 < 40 < 50 < 60.
Und auch 10 < 20 < 21 < 40 < 50 < 60.
Falsch ist 10 < 20 < 20 < 40 < 50 < 60.
Vergrößert man einen Ausdruck irgendwo in der Mitte, dann muss man nach rechts sehen.
Verkleinert man einen Ausdruck irgendwo in der Mitte, dann muss man nach links sehen.
Bei ">" statt "<" natürlich entgegengesetzt.

Und noch etwas: wenn man Änderungen am Anfang oder am Ende der Ungleichung vornimmt,
dann sollte man bedenken, dass die zunächst gestellte Aufgabe zu einer anderen wird.
Also 9 < 61 ist ebenfalls richtig, aber eine andere Aufgabe.


Aber nun zum Beispiel.

Folgende Vorgehensweise ist bei Ungleichungen empfehlenswert:
Man zieht die Induktionsbehauptung auseinander und setzt die Induktionsvoraussetzung in die Mitte.
Anschließend versucht man die Anpassung z.B. der linken Seite der IV an die linke Seite der IB.
Das führt bei der IV zu einer Erweiterung, auf beiden Seiten gleich sein sollte.
An die Stelle der Punkte treten dann Umformungen.

Beweisen Sie: \(2^n > n^2 ~\) für alle n > 4.

Induktionsanfang

n=5

\(2^5 > 5^2 ~\) ==> 32>25. Wahre Aussage.


Induktionsschluss

- Induktionsvoraussetzung:

\(2^k > k^2 ~\)

- Induktionsbehauptung:

\(2^{(k+1)} > (k+1)^2 ~\)

Beweis der Induktionsbehauptung mit Anwendung der Induktionsvoraussetzung:

\( 2^{(k+1)} \)
\( \geq \)             Auch ein "=" wäre ausreichend.
.
.
.
.
\(2^k ~\)
>
\( k^2 ~\)
.
.
.
.
\( \geq \)             Auch ein "=" wäre ausreichend.
\( (k+1)^2 ~\)


Die Punkte werden jetzt ersetzt durch Umformungen.
Die Induktionsvoraussetzung erweitert sich auf beiden Seiten mit zwei.
Nochmal von vorne:

\( 2^{(k+1)} \)
=
\( 2*2^k \)
>
\(2*k^2 \)
                              Auf keinen Fall darf sich die Induktionsvoraussetzung einseitig ändern,
                              sie könnte falsch werden. Und außerdem ist sie bis jetzt noch
                              nicht einmal bewiesen. Deshalb die Multiplikation auch von \(k^2\) mit zwei.

\(2*k^2 \)
=
\(k^2+~~~~~k^2 \)
                             
                              ----------------------------------------------------------------------
                              Hier findet eine v.I. innerhalb der v.I. statt!
                              Schiel auf das Ziel!
                              Das "\({2*k+1}\)" wurde von unten geholt.
                              Zu beweisen: \(k^2 \geq {2*k+1}\) für alle \(k > 4\).

                              Induktionsanfang

                              \( 5^2>11 \). Wahre Aussage.

                              Induktionsschluss

                              Induktionsvoraussetzung:

                              \(k^2 \geq {2*k+1}\)

                              Induktionsbehauptung:

                              \((k+1)^2 \geq {2*(k+1)+1}\)



                              Beweis der Induktionsbehauptung:

                              \((k+1)^2\)
                              \(\geq \)
                             
                             
                             
                              \(k^2 \)
                              \(\geq \)
                              \({2*k+1}\)
                             
                              Ausrechnen des Binoms ist gleich Erweiterung der IV mit \(+2*k+1 \)
                             
                              \(k^2+2*k+1 \)
                              \(\geq \)
                              \(2*k+1 +2*k+1\)

                              \(\geq \)
                              \(4*k+2\)

                              \(> \)
                              \(2*k+3\)
                              \(= \)
                              \(2*(k+1)+1\)

                              Somit dürfen wir das Größerzeichen, aber auch das
                              Größergleichzeichen und selbst das Gleichheitszeichen
                              in die Induktion kurz vor dem Ende eintragen.
                              Wegen ">" in der IV wäre ein Gleichheitszeichen ausreichend.
                              ----------------------------------------------------------------------

\(k^2+~~~~~k^2 \)
\(\geq \)

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


q.e.d.