Ich habe folgenden Algorithmus (Pythoncode):
def f(n):
w = 0 # Anfangswert
for i in range(n+1): # i=0,...,(n+1)-1
w = w+i # w um i erhöhen
return w # Nach Beendigung der for-Schleife w zurückgeben.
Dieser Berechnet die Summe aller Zahlen 0,...,n .
Ich habe dazu folgende Schleifeninvariante aufgestellt:
$$ w'=\sum_{i=0}^n i-\sum_{k=i+1}^n k=\frac{n\cdot (n+1)+(i-n)\cdot (n+i+1)}{2} $$
Nur leider geht mein Induktionsbeweis nicht auf, verstehe aber nicht wiso.
Induktionsanfang. Für i=0 ist beim ersten Schleifendurchlauf $$ w'=\sum_{i=0}^n i-\sum_{k=0+1}^n k=\sum_{i=0}^n i-\sum_{k=1}^n k=0=\frac{n\cdot (n+1)+(0-n)\cdot (n+0+1)}{2}. $$
Induktionsvoraussetzung. Angenommen, die Schleifeninvariante gelte für den ersten Schleifendurchlauf.
Induktionsschritt. Dann gilt diese auch für den nachfolgenden, also für die (i+1)-te Iteration, also:
$$ w'=\sum_{i=0}^n i-\sum_{k=(i+1)+1}^n k=\frac{n\cdot (n+1)+((i+1)-n)\cdot (n+(i+1)+1)}{2}\\=\sum_{i=0}^n i-\sum_{k=i+2}^n k=\frac{n\cdot (n+1)+(i+1-n)\cdot (n+i+2)}{2}=\underline{\frac{i^2+3\cdot i+2}{2}} $$ Dies zeigt man so:
$$ w'=w+i\stackrel{(IV)}{=} \Bigg(\sum_{i=0}^n i-\sum_{k=i+1}^n k\Bigg)+i=\frac{n\cdot (n+1)+(i-n)\cdot (n+i+1)}{2}+i\\=\underline{\frac{i^2+3\cdot i}{2}} $$
Was mache ich falsch?