BANEKO GmbH
Zurück   Weiter

Beispiel 1

In diesem Beispiel soll die bekannte Formel

  A(n):      
n
∑
k=1
k  =  
n (n+1)
2
      (1)

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

1
∑
k=1
k  =  1  =  
1 · 2
2
 

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

A(n):      
n
∑
k=1
k  =  
n (n+1)
2
 

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

  A(n+1):      
n+1
∑
k=1
k  =  
(n+1) (n+2)
2
     (2)

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

(n+1) (n+2)
2
 =  
(n+1) n + (n+1) 2
2
 =
(n+1) n
2
 + 
(n+1) 2
2
 = 
n (n+1)
2
 + (n+1) 

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

(n+1) (n+2)
2
 = 
n (n+1)
2
 + (n+1) = 
n
∑
k=1
k  + (n+1) 

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

(n+1) (n+2)
2
  =  
n+1
∑
k=1
k  

Damit ist die Aussage A(n) für alle n ≥ 1 gezeigt.

Zurück   Weiter