Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03370.jsonl.gz/2038

Zurück
Weiter
Beispiel 1
In diesem Beispiel soll die bekannte Formel
bewiesen werden. Diese kann man bekanntlich direkt herleiten, aber hier geht es darum, an einem möglichst einfachen Beispiel den Mechanismus der Induktion vorzustellen.
Induktionsanfang
Wir wählen als Induktionsanfang den Wert n0 = 1, da die Formel für n = 0 keinen Sinn macht.
Einsetzen von 1 in die Formel liefert die offensichtlich wahre Aussage
Damit ist die Aussage A(1) war.
Tipp: Oft scheint die Aussage der Induktionsverankerung völlig trivial. Trotzdem darf man nicht vergessen, diese anzugeben und auch angeben, dass man ihre Gültigkeit erkannt hat.
Induktionsannahme
Nun nehmen wir an, dass im weiteren die Aussage
für ein beliebiges, aber fest gewähltes n
wahr sei.
Tipp: Wir haben die Aussage A(n) nicht bewiesen, wir setzen statt dessen ihre Gültigkeit voraus. Für die Variable n haben wir einen festen Wert gewählt, sie ist also im Folgenden eine Konstante.
Induktionsschritt
Nun müssen wir die Aussage
zeigen. Dafür beginnen wir auf einer Seite der Formel und versuchen die andere Seite daraus herzuleiten. Dabei ist es essentiell, auf die Induktionsannahme A(n) zurückzugreifen.
Wir beginnen mit der rechten Seite der Formel für A(n+1)
und multiplizieren die zweite Klammer aus. Es gilt
Damit haben wir in der rechten Seite der Aussage A(n+1) die rechte Seite von A(n) isoliert. Da nach Induktionsvoraussetzung A(n) gilt, dürfen wir diese durch ihre linke Seite ersetzen. Wir erhalten nun
Zieht man nun noch den einzelnen Summanden (n+1) in das Summenzeichen, indem man die obere Indexgrenze vergrößert, hat man den Induktionsschritt gezeigt. Es gilt also
Damit ist die Aussage A(n) für alle n ≥ 1 gezeigt.
Zurück
Weiter