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 wird bewiesen: \(\frac{4^n}{n+1} ~ < ~ \frac{(2n)!}{(n!)^2}\) für alle n \( \geq{2} \)

Empfehlung: Diese Seite entweder Ausdrucken oder Abschreiben!


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}\)


Wenn alle Pünktchen in der Spalte durch die Zeichen "\(<\)", "\(\leq\)" oder "\(=\)" ersetzt werden können,
ist der Induktionsschluss fertig. Es reicht in der Kette ein einziges "\(<\)" aus, alle anderen Zeichen
können "\(=\)" sein. Zunächst formen wir um bis einschließlich der IV.

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

            =

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

            =                 Wir arbeiten auf die linke Seite der IV hin,
                                wir brauchen im Nenner \(k+1 \), deshalb die Erweiterung.

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

            =               Faktorentausch in Zähler und Nenner ergibt

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

            =

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

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

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





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



Damit ist alles gezeigt. q.e.d.





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





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





Beide Seiten erweitern mit \((k+1)(k+2)\) ergibt




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





Es muss gesichert sein, dass der rechte Faktor aus der IV




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





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





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





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





2.2.) =\(\frac{(2k+2)!}{k!(k+1)k!(k+1)}\)   Das Ausklammern von Fakultäten ist oben erklärt.



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





Schlussbemerkung:

In diesem Beispiel ist es zweckmäßig, einen Sprung nach unten zu machen und die Umformungen
in Gegenrichtung vorzunehmen. Die Zwischenschritte von 2.9.) bis 2.1.) in Abwärtsrichtung zu ermitteln
dürfte so gut wie unmöglich sein.


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