Einstieg in ...   Mathematik, vollständige Induktion




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.
In diesem Beispiel kann man die Aktionen von oben nach unten nachvollziehen,
aber es dürfte schwer bis unmöglich sein, die Ideen dazu selbst zu haben.

Wichtig bei Ungleichungen: die Kette innerhalb eines Beweises darf entweder nur
eine Kombination aus \(<~\leq~=~\) sein (ein Größergleichzeichen oder Größerzeichen
darf nicht auftreten) oder es gilt z.B. \(\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.