Einstieg in ...   Mathematik, vollständige Induktion




Die vollständige Induktion



Die vollständige Induktion ist ein Verfahren, mit dem eine Aussage
für alle natürlichen Zahlen n, die größer oder gleich einem bestimmten
Anfangswert sind, bewiesen werden soll. Das Adjektiv "vollständig"
wird in der französischen und englischen Sprache nicht verwendet,
man spricht hier vom "preuve par induction" oder "Mathematical Induction".

Die vollständige Induktion besteht aus zwei Teilen:

- dem Induktionsanfang sowie
- dem Induktionsschluss (manchmal auch Induktionsschritt genannt).

In unserem einführenden Beispiel werden wir die übliche Reihenfolge
absichtlich verändern, wir beginnen ausnahmsweise mit dem Induktionsschluss,
dann folgt der Induktionsanfang. Aber zunächst einige

Vorbemerkungen

Schauen wir einfach mal folgende Partialsummen an:

a) 1 + 3 = 4
b) 1 + 3 + 5 = 9
c) 1 + 3 + 5 + 7 = 16
d) 1 + 3 + 5 + 7 + 9 = 25
e) 1 + 3 + 5 + 7 + 9 + 11 = 36
f) 1 + 3 + 5 + 7 + 9 + 11 + 13 = 49
g) 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64
h) 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81

Es ist hier so, dass wir z.B. das Ergebnis von f) in g) weiterverwenden können,
wir brauchen also nicht aufs neue 1 + 3 + 5 + 7 + 9 + 11 + 13 zu berechnen
sondern verkürzen auf 49 + 15 = 64. Und genauso von g) nach h) mit 64 + 17 = 81.
Weiterhin sehen wir, dass auf der rechten Seite die Quadratzahlen von 2*2 bis 9*9
stehen. Wir kommen darauf zurück.

Und nun zu unserem ersten Beispiel, im Internet schon über 1000 mal vorgeführt,
die sogenannte "Gaußsche Summenformel".

Sie ist benannt nach dem wohl größten Mathematiker aller Zeiten Carl Friedrich Gauß
(1777-1855). Der bekam bereits als kleines Kind von seinem Lehrer die Aufgabe,
alle Zahlen von 1 bis 100 zusammenzuzählen. Also 1 + 2 + 3 + 4 + ... + 99 + 100.
Gauß änderte die Reihenfolge auf (100 + 1) + (99 + 2) + (98 + 3) + ... + (51 + 50).
In jeder Klammer steht jetzt 101, so dass er die Rechnung verkürzte und das Produkt
aus 101*50 (= 5050) berechnete.

Wenn man nur bis zur 99 aufaddieren will, dann sieht die Paarbildung etwas anders aus,
nämlich (99 + 1) + (98 + 2) ... bis zu + (51 + 49). Die alleinstehende 50 wird dann
zum Schluß addiert. Das Ergebnis ist also 100*49 + 50 = 4950.
Mit diesen Überlegungen kann man eine Gleichung aufstellen, die auf der rechten
Seite eine "Turbo-Formel" enthält, mit der sich erheblich schneller rechnen läßt:

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}~.\)

Wenn man alle Zahlen von 1 bis 200 addieren will, dann rechnet man 200*(200+1):2.
Aber ist diese Formel für alle n korrekt? Das soll jetzt bewiesen werden.




1. Beispiel:

Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n \( \geq{1} \) gilt:

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}~.\)

Wir fangen (ausnahmsweise) mit dem Induktionsschluss an. Wir schreiben zuerst die sogenannte
Induktionsvoraussetzung (manchmal auch Induktionsannahme genannt) auf. Das ist nichts anderes,
als ein Abschreiben der Aufgabe. Wir benennen hier das "n" um in "k", um zu zeigen, dass
die Aussage für eine beliebige Zahl gelten soll und (noch) nicht für alle Zahlen. Viele Autoren
verzichten auf die Umbuchstabierung. Außerdem setzen wir ein Fragezeichen über das Gleichheitszeichen.


Induktionsschluss

- Induktionsvoraussetzung:

Wenn eine Aussage für alle natürlichen Zahlen gelten soll, dann muss sie auch für ein
beliebiges n=k gelten.

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k \stackrel{?}{=} \frac{k*(k+1)}{2}\) .

- Induktionsbehauptung:

Wenn eine Aussage für alle natürlichen Zahlen gelten soll, dann muss sie auch für den Nachfolger
k+1 gelten. Das nennen wir die Induktionsbehauptung. Empfehlung: IMMER k+1 in Klammern setzen!

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k ~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}\)

Die Anwendung der Induktionsvoraussetzung führt zu Folgendem:

\(\underbrace{ 1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ k }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} ~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}\)

\(~~~~~~~~~~~~~~~~~~~\frac{k*(k+1)}{2}\, ~~~~~~~~~~~~~~~~~~~~~~ + ~ (k + 1) \stackrel{?}{=} \frac{(k+1)*((k+ 1)+1)}{2}\)

Jetzt werden beide Seiten der Gleichung umgeformt, links wird erweitert, rechts Klammern aufgelöst:

\(~~~~~~~~~~~~~~~~~~~\frac{k*(k+1)}{2}\, ~~~~~~~~~~~~~~~~~~~~~~ + \frac{2*(k+1)}{2}\,~ \stackrel{?}{=} \frac{(k+1)*(k+2)}{2}\)

In allen Zählern die Klammern beseitigen:

\(~~~~~~~~~~~~~~~~~~~~\frac{k^2+k}{2}\, ~~~~~~~~~~~~~~~~~~~~~~~~~ + \frac{2k+2}{2}\,~~~~ \stackrel{?}{=} \frac{k^2+k+2k+2}{2}\)

Auf beiden Seiten den Nenner entfernen und die Zähler optimieren führt zu:

\(k^2~+~3k~+2~=~k^2~+~3k~+2 \)

Die Induktionsbehauptung ist bewiesen, Bedingung ist die Richtigkeit der Induktionsvoraussetzung.
Wir sind daher noch nicht fertig. Jetzt ist eine Dominosteinkette aufgestellt, die Steine stehen
senkrecht und dicht genug nebeneinander. Wir wissen bis jetzt: Wenn der 27. Stein umfällt, dann fällt
auch der nachfolgende 28. Stein um. Wenn der 142.367. Stein umfällt, dann fällt auch der 142.368.
Stein um. Und wenn der erste Stein umfällt, dann fällt auch der zweite Stein um. Wir müssen
zeigen, DASS ein erster Dominostein umfällt. Das ist unser Induktionsanfang.


Induktionsanfang

Zunächst versuchen wir, den 5. Dominostein zu kippen und mit n=5 erhalten wir:

\(1 + 2 + 3 + 4 + 5 ~ = \frac{5*(5+1)}{2}~.\)

Das ergibt auf beiden Seiten fünfzehn. Der 5. Dominostein ist gefallen und alle nachfolgenden
ebenfalls. Die Aussage ist bewiesen für alle n größer oder gleich fünf. Die Aufgabe verlangte
jedoch die Untersuchung für alle n größer oder gleich eins. Also setzen wir n=1 ein.

\(1 ~ = ~ \frac{1*(1+1)}{2}\)

1 = 1, wahre Aussage.

Mit Hilfe von Induktionsanfang und Induktionsschluss ist jetzt gezeigt:

\(1 + 2 + 3 + 4 + 5 + ~ ... ~ + ~ n = \frac{n*(n+1)}{2}\)

ist gültig für alle natürlichen Zahlen n.


Wichtig: ein Induktionsanfang ist zwingend erforderlich. Wenn dieser fehlt, ist alles andere
wertlos und der Beweis ist nicht erbracht.




2. Beispiel:

Folgendes ändern wir jetzt: wir beginnen mit dem Induktionsanfang. Wir setzen keine Fragezeichen
in Gleichungen. Wir formen diesmal nur die linke Seite der Induktionsbehauptung um. Das erfordert,
dass man die Möglichkeiten des Ausklammerns und binomische Formeln erkennt.

Beweisen oder widerlegen Sie, dass für alle natürlichen Zahlen n \( \geq{1} \) gilt:

\(1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ n^3 = \frac{n^2(n+1)^2}{4}~.\)


Induktionsanfang

Wir setzen n=1:

\(1^3 ~ = \frac{1^2(1+1)^2}{4}\,\)

1=1, wahre Aussage.


Induktionsschluss

- Induktionsvoraussetzung:

\(1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 = \frac{k^2(k+1)^2}{4}~.\)

- Induktionsbehauptung:

\(1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}~.\)

Beweis der Induktionsbehauptung mit Anwendung der Induktionsvoraussetzung:

\(\underbrace{1^3 + 2^3 + 3^3 + 4^3 + 5^3 + ~ ... ~ + ~ k^3 }_{Die ~ rechte ~ Seite ~ der ~ IV ~ einsetzen} + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}\)

\(\frac{k^2(k+1)^2}{4}\, + ~(k+1)^3 ~ = \frac{(k+1)^2((k+1)+1)^2}{4}~.\)

Umformen der linken Gleichungsseite:

\(\frac{k^2(k+1)^2}{4}\, + ~ \frac{4(k+1)^3}{4} ~ \), Erweitern des zweiten Summanden

\(=\frac{k^2(k+1)^2\, + ~ 4(k+1)^3}{4} ~ \)

\(=\frac {(k+1)^2 [k^2+4(k+1)]} {4} ~ \), Ausklammern von \((k+1)^2\)

\(=\frac {(k+1)^2 (k^2+4k+4)} {4} ~ \), Binom im zweiten Faktor erkennen

\(=\frac {(k+1)^2 (k+2)^2} {4} ~ \)

\(=\frac {(k+1)^2 ((k+1)+1)^2} {4} ~ \)

Und das ist gleich der rechten Seite der Induktionsbehauptung.     q.e.d.


Anmerkung: alternativ kann man auf beiden Seiten der IB die Klammern entfernen wie im ersten Beispiel.
Dabei kann man sich jedoch leichter verrechnen. Nach Beseitigung der Nenner lautet die IB jetzt:

\(k^2(k+1)^2 + 4(k^3+3k^2+3k+1)~ = ~(k+1)^2(k+2)^2 \)

\(k^2(k^2+2k+1)+4k^3+12k^2+12k+4~ = ~ (k^2+2k+1)(k^2+4k+4)\)

\(k^4+2k^3+k^2+4k^3+12k^2+12k+4 ~ = ~ k^4+2k^3+k^2+4k^3+12k^2+12k+4 \)




3. Beispiel:

Auch Teilbarkeiten lassen sich mit Hilfe der vollständigen Induktion beweisen.
Meistens wenden wir die Induktionsvoraussetzung erst am Ende an. Das Vorgehen ist
weitgehend gleich: wenn jeder Summand durch eine Zahl teilbar ist, dann ist auch
die gesamte Summe durch diese Zahl teilbar. Bei den Umformungen ist es Ziel, dass die
Induktionsvoraussetzung wieder zum Vorschein kommt.

Beweisen Sie, dass \(3*4^n+6 \) für alle natürlichen Zahlen n \( \geq{1} \) durch 9 ohne Rest teilbar ist.


Induktionsanfang

n=1

\(3*4^1+6 = 18\), durch 9 teilbar. Wahre Aussage.


Induktionsschluss

- Induktionsvoraussetzung:

\(3*4^k+6 \) ist durch 9 teilbar.

- Induktionsbehauptung:

\(3*4^{(k+1)} +6 \) ist durch 9 teilbar.

\(3*4*4^k +6 \) Anwendung der Potenzgesetze

Um die IV anwenden zu können, müssen wir die 4 ausklammern, erhöhen der 6 auf 24 durch Addition von 18-18.

\(3*4*4^k +6~~~ +18-18 \)

\(3*4*4^k +24~~~ -18 \)

\(4*(3*4^k +6)~~ -18 \)

Wegen der IV ist der erste Summand durch 9 teilbar. Der zweite Summand ist durch 9 teilbar.

Also ist der gesamte Ausdruck durch 9 teilbar.      q.e.d.




4. Beispiel:

Beweisen Sie, dass \(7^n-2^n \) für alle natürlichen Zahlen n \( \geq{1} \) durch 5 ohne Rest teilbar ist.


Induktionsanfang

n=1

\(7^1-2^1 \) = 5, durch 5 teilbar. Wahre Aussage.


Induktionsschluss

- Induktionsvoraussetzung:

\(7^k-2^k \) ist durch 5 teilbar.

- Induktionsbehauptung:

\( 7^{(k+1)}-2^{(k+1)} \) ist durch 5 teilbar.

\(7*7^k-2*2^k \)

Ziel soll sein, die IV sichtbar machen, den ersten Faktor 7 zerlegen in 5 + 2.

\((5+2)*7^k-2*2^k \)

\(5*7^k+2*7^k-2*2^k \)

\(5*7^k+2*(7^k-2^k) \)

Der erste Summand ist durch 5 teilbar. Mit der IV ist auch der zweite Summand durch 5 teilbar.

Also ist der gesamte Ausdruck durch 5 teilbar.      q.e.d.




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.




6. Beispiel:

Wir wiederholen kurz Fakultäten:

6! = 6*5*4*3*2*1 = 720

8! = 8*7*6*5*4*3*2*1 = 40.320

Definition: 0! = 1 (Es gibt genau eine Möglichkeit, keinen Schüler an keinen Tisch zu setzen).

Beispiel für Ausklammern: (2n+2)! = (2n)!*(2n+1)*(2n+2)

Für n=5 erhalten wir 12! = 10! *11 *12 = 479.001.600


In diesem letzten Beispiel beweisen wir:

\(\frac{4^n}{n+1} ~ < ~ \frac{(2n)!}{(n!)^2}\) für alle n \( \geq{2} \)


Induktionsanfang

n=2:

\(\frac{4^2}{2+1} ~ < ~ \frac{(2*2)!}{(2!)^2}\)

\(\frac{16}{3} ~ < ~ \frac{24}{4}\). Wahre Aussage.

Induktionsschluss

- Induktionsvoraussetzung:

\(\frac{4^k}{k+1} ~ < ~ \frac{(2k)!}{(k!)^2}\)

- Induktionsbehauptung:

\(\frac{4^{(k+1)}} {k+2} ~ < ~ \frac{(2(k+1))!}{((k+1)!)^2}\)

Beweis der Induktionsbehauptung mit Anwendung der Induktionsvoraussetzung:

Wieder ziehen wir die IB auseinander und setzen die IV in die Mitte.

\(\frac{4^{(k+1)}} {k+2} \)
.
.
.
\(\frac{4^k}{k+1}\)
<
\(\frac{(2k)!}{(k!)^2}\)
.
.
.
\(\frac{(2(k+1))!}{((k+1)!)^2}\)


------------------------------------------------------------------------------------------------------------------------

                              Zunächst formen wir um bis einschließlich der IV.

\(\frac{4^{(k+1)}} {k+2} \)
=
\(\frac{4*4^{k}} {k+2} \)

=                           Schiel auf das Ziel, wir brauchen im Nenner \(k+1 \).
                              Deshalb die Erweiterung mit \(k+1 \).

\(\frac{4*4^{k}} {k+2} \) * \(\frac{k+1} {k+1} \)

=                           Faktorentausch in Zähler und Nenner ergibt

\(\frac{4^{k}} {k+1} \) * \(\frac{4*(k+1)} {k+2} \)

<                           Nun multiplizieren wir 4*(k+1)/(k+2) an die rechte Seite der IV,
                              da sich die Aussage der IV nicht verändern darf.

\(\frac{(2k)!}{(k!)^2}\) * \(\frac{4*(k+1)} {k+2} \)





!!!!!! Wir gehen jetzt nach unten und nehmen von dort bis zur Mitte Umformungen vor !!!!!!



Damit ist alles gezeigt.

\(4k^2+8k+4 \leq 4k^2+10k+4\)

\((4k+4)(k+1) \leq (4k+2)(k+2)\)

Antwort: über Kreuz malnehmen ergibt

\(\frac{4*(k+1)}{k+2}\) kleiner oder gleich \(\frac{4k+2}{k+1}\) ist.

Es verbleibt zum Schluss die Frage, ob

\(\frac{(2k)!}{(k!)^2} * \frac{4k+2}{k+1}\)

=

\(\frac{(2k)!}{(k!)^2} * \frac{(2k+1)*2}{(k+1)}\)

=

\(\frac{(2k)!}{(k!)^2} * \frac{(2k+1)*2(k+1)}{(k+1)^2}\)

=

\(\frac{(2k)!(2k+1)(2k+2)}{(k!)^2(k+1)^2}\)

=

\(\frac{(2k+2)!}{k!(k+1)k!(k+1)}\)

=                           Das Ausklammern von Fakultäten ist oben erklärt.

\(\frac{(2(k+1))!}{((k+1)!)^2}\)


Schlussbemerkung:

Manchmal ist es zweckmäßig, die Umformungen in Gegenrichtung vorzunehmen.
Umgekehrt, von oben nach unten, kann man die Aktionen nachvollziehen,
aber es dürfte schwer bis unmöglich sein, diese selbst vorzunehmen.

Wichtig bei Ungleichungen: innerhalb eines Beweises ist nur
eine Kombination aus \(<~<~\leq~=~\leq~\leq~=~=~ \) möglich. Ein Größergleichzeichen
oder Größerzeichen darf nicht auftreten. Umgekehrt gilt \(\geq~=~\geq~=~>~\geq~>~=~ \),
dann ist ein Kleinergleich- oder Kleinerzeichen nicht zulässig.

Und jetzt viel Erfolg bei den Übungen, es gibt im Internet sehr viele davon.