Induction

Mathematical Induction Example 2 --- Sum of Squares

Problem: For any natural number n , 1² + 2² + ... + n² = n( n + 1 )( 2n + 1 )/6.

Proof:
Basis Step: If n = 0, then LHS = 0² = 0, and RHS = 0 * (0 + 1)(2*0 + 1)/6 = 0 .
Hence LHS = RHS.
Induction: Assume that for an arbitrary natural number n,
1² + 2² + ... + n² = n( n + 1 )( 2n + 1 )/6. -------- Induction Hypothesis
To prove this for n+1,   first try to express LHS for n+1   in terms of LHS for n,   and use the induction hypothesis.
Here let us try
      LHS for n + 1 = 1² + 2² + ... + n² + (n + 1)² = ( 1² + 2² + ... + n² ) + (n + 1)²
Using the induction hypothesis, the last expression can be rewritten as
      n( n + 1 )( 2n + 1 )/6 + (n + 1)²
Factoring (n + 1)/6 out, we get
      ( n + 1 )( n( 2n + 1 ) + 6 ( n + 1 ) )/6
       = ( n + 1 )( 2n² + 7n + 6 )/6
       = ( n + 1 )( n + 2 )( 2n + 3 )/6 ,
which is equal to the RHS for n+1.

Thus LHS = RHS for n+1.

End of Proof.