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

(2r³ + 9r² +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² + 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.