Bevor ich durch den Wikipedia-Artikel auf die Bedeutung des "doppelten Abzählens" aufmerksam gemacht wurde, hatte ich folgenden Kommentar verfasst; und ehe ich ihn ganz in die Tonne kloppe gebe ich ihn hier noch eben zum Besten :
∑ [k=1 .. m] k = m*(m+1) / 2 wird vorausgesetzt.
Damit folgt, dass ∑ [k=i .. n] k
= ∑ [k=1 .. n] k - ∑ [k=1 .. i-1] k
= n*(n+1) / 2 - (i-1)*i / 2 ist.
Das Schema
1+2+3+ ... +n
+ 2+3+ ... +n
+ 3+ ... +n
...
+ n
kann auf zweifache Art (heißt das "doppelt" ?) abgezählt werden :
Spaltenweise ergibt sich 1*1 + 2*2 + 3*3 + ... + n*n , also die Summe
∑ [i=1 .. n] i^2
Zeilenweise sind es Summen, die von i bis n laufen, und alle diese Summen werden von 1 bis n addiert, also die Summe ∑ [i=1 .. n] ( ∑ [k=i .. n] k )
⇒ ∑ [i=1 .. n] i^2
= ∑ [i=1 .. n] ( ∑ [k=i .. n] k )
= ∑ [i=1 .. n] ( n*(n+1) / 2 - (i-1)*i / 2 )
= ∑ [i=1 .. n] n*(n+1) / 2 - ∑ [i=1 .. n] (i^2 - i) / 2
= n * n*(n+1) / 2 - 1/2 * ∑ [i=1 .. n] i^2 + 1/2 * ∑ [i=1 .. n] i
⇒ 3/2 * ∑ [i=1 .. n] i^2 = n * n*(n+1) / 2 + 1/2 * n*(n+1)/2
⇒ ∑ [i=1 .. n] i^2 = 2/3 * ( n * n*(n+1) / 2 + 1/2 * n*(n+1)/2 )
= 2/3 * (n^3/2 + n^2/2 + n^2/4 + n/4)
= n^3/2 + n^2/3 + n^2/6 + n^/6
= 1/6 (2n^3 + 3n^2 + n)
