Induction

An Illustration Using the Sum of Squared Integers

Examples                                                                             Rule  

1                5                14                                          n(n+1)(2n+1)/6    

n                number of  squares                                            

1                2                3

1                1 + 4           1 + 4 + 9

 

n Value                Formula Value

1                                                                     1(2)(3)/6 = 1

2                                                                     2(3)(5)/6 = 5

3                                                                     3(4)(7)/6 = 14

 

Proof (By Induction)

Suppose rule is true for n = r. Does that mean it is true for n =  r + 1 ?

Substitute (r + 1) for n in the above rule. By the idea of the rule (sum of squared integers) we need see:

 

r(r +1)(2r + 1)/6  + (r + 1)2 =  [r( 2r2  +3r + 1)/6] + [r2  + 2r + 1] =

(2r3 + 9r2  +13r  + 6 )/6        ***

We need to determine if this is the same as the rule with n = r + 1 .

(r + 1)(r + 2)(2r + 3)/6  =

(r2  + 3r + 2)(2r + 3)/6                      Multiplying out the two factors we see that it is the *** expression.

 

Then the inductive proof uses the fact that truth for n = r implies the rule is valid for n = r + 1.

 

Here is the actual reasoning:

 

But the rule holds for n = 1, 2, and 3. Therefore it holds for n= 4, 5, É or any positive integer n.