Einstieg in ...   Mathematik, vollständige Induktion


Beispiel 6:

Fakultät wächst schneller als Potenz



Empfehlung vorneweg: Diese Seite sollte man entweder ausdrucken oder teilweise abschreiben!

Wir wiederholen kurz Fakultäten:

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

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

Was ergibt (7!)/(5!)? Hinweis: Per Anhalter durch die Galaxis.

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


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


In der Mitte steht bereits ein "\(<\)".
Wenn alle Pünktchen in der Spalte mindestens durch ein "\(=\)"
ersetzt werden können, ist der Induktionsschluss fertig.
Zunächst formen wir um bis einschließlich der IV.

Noch einmal von vorne:

\(\frac{4^{(k+1)}} {k+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.

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

            =

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

            <                 Wir haben (4*k+4)/(k+2) an die linke Seite der IV multipliziert,
                                das müssen wir auch an der rechten Seite der IV machen,
                                da sich die Aussage der IV nicht verändern darf.

\(\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.





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





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





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




\(\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




=\(\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:

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


Und jetzt viel Erfolg bei weiteren Übungen, es gibt im Internet sehr viele davon!



>> Weitere Aufgaben und Lösungen