Definitionen:
⟪ {: ( f(n) := (sum_(i=1)^n i)^2 , = , ( 1 + 2 + … + n )^2 ), ( g(n) := sum_(i=1)^n i^3 , = , 1³ + 2³ +… + n³ ) :} ⟫
Zu zeigen:
⟪ ∀ n∊ℕ : f(n) = g(n) ⟫
Die Aussage gilt trivial für ⟪n=1⟫:
⟪f(1) = (sum_(i=1)^1 i)^2 = (1)^2 = 1 = (1^3) = sum_(i=1)^1 n³ = g(1)⟫
Induktionsschritt von ⟪n⟫ auf ⟪n+1⟫:
⟪ {: ( f(n+1) , = , ( sum_(i=1)^(n+1) i )^2 ) :} ⟫
Wir trennen den letzten Summanden ⟪n+1⟫ ab:
⟪ {: ( f(n+1) , = , ( ubrace( sum_(i=1)^(n ) i )_a + ubrace( (n+1) )_b )^2 ) :} ⟫
Anwendung der ersten binomischen Formel ⟪(a+b)² = a² +2ab + b²⟫ ergibt:
⟪ {: ( f(n+1) , = , ubrace( (sum_(i=1)^(n ) i )^2 )_(a²) + ubrace(2)_2 * ubrace(sum_(i=1)^n i)_a * ubrace((n+1))_b + ubrace((n+1)^2)_(b²) ) :} ⟫
Der Term ⟪a²⟫ ist offensichtlich gleich ⟪f(n)⟫:
⟪ {: ( f(n+1) , = , f(n) + 2 * sum_(i=1)^n i * (n+1) + (n+1)^2 ) :} ⟫
Mit ⟪sum_(i=1)^n i = n/2(n+1)⟫ erhalten wir:
⟪ {: ( f(n+1) , = , f(n) + cancel(2) * n/cancel(2)*(n+1) * (n+1) + (n+1)^2 ), ( , = , f(n) + n * (n+1)^2 + 1 * (n+1)^2 ), ( , = , f(n) + (n+1) * (n+1)^2 ), ( , = , f(n) + (n+1)^3 ) :} ⟫
Mit der Induktionsvoraussetzung ⟪f(n)=g(n)⟫ ergibt sich:
⟪ {: ( f(n+1) , = , g(n) + (n+1)^3 ), ( , = , sum_(i=1)^n i^3 + (n+1)^3 ) :} ⟫
Wir nehmen den Term ⟪(n+1)^3⟫ in die Summe auf:
⟪ {: ( f(n+1) , = , sum_(i=1)^(n+1) i^3 ), ( , = , g(n+1) ∎ ) :} ⟫