**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( 2r^{2 }+3r + 1)/6] + [r^{2 }+ 2r + 1] =

(2r^{3} + 9r^{2 } +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
=

(r^{2}^{ } + 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, etc. In other words, for any positive integer n.